What is the brute force approach and complexity for Subtree of Another Tree?

Run Same Tree from every node of root against subRoot with time complexity O(M · N) and space complexity O(H).

How do you identify the pattern for Subtree of Another Tree?

Look for key signals in the prompt: "subtree of another tree" indicates A whole block of tokens in root's preorder text. The top value alone is not enough; the whole block has to match.; "same structure and node values" indicates Shape and values together. The # markers encode the shape, and the values are the text.; "root and subRoot" indicates Two sequences: this is a pattern search, the same as searching for one string inside another..

Subtree of Another Tree

Easy·LeetCode #572 Pro OnlyPattern Transfer

LeetCode

Problem Statement

You are given two binary trees, root and subRoot. Decide whether subRoot appears inside root: some node of root must have a subtree with exactly the same shape and the same values as subRoot.

A node together with all of its descendants is a subtree. The whole tree counts as a subtree of itself.

Input

Two roots, root and subRoot. Both trees have at least one node.

Output

true if some subtree of root matches subRoot exactly, false otherwise.

Example 1

Input: root = [3, 4, 5, 1, 2], subRoot = [4, 1, 2]

Output: true

The node 4 with its two children 1 and 2 is exactly subRoot.

Example 2

Input: root = [3, 4, 5, 1, 2, null, null, null, null, 0], subRoot = [4, 1, 2]

Output: false

The node 4 has the same value and the same first two children, but the node 2 has an extra child 0. The subtree is not an exact match.

Constraints

• The number of nodes in root is in the range [1, 2000].
• The number of nodes in subRoot is in the range [1, 1000].
• −10^4 ≤ root.val ≤ 10^4
• −10^4 ≤ subRoot.val ≤ 10^4

Pattern Recognition Clues

Recognising these key signals in the problem description immediately identifies the pattern:

“subtree of another tree”

→ A whole block of tokens in root's preorder text. The top value alone is not enough; the whole block has to match.

“same structure and node values”

→ Shape and values together. The # markers encode the shape, and the values are the text.

“root and subRoot”

→ Two sequences: this is a pattern search, the same as searching for one string inside another.

Approach Complexity Ladder

Brute Force — Same Tree at every nodeO(M · N)O(H)

Run Same Tree from every node of root against subRoot

Optimal — serialize both trees, then search with KMPO(M + N)O(M + N)

Write both trees as preorder text with a comma before each token and # for empty children, then search with KMP

Brute Force Intuition

A matching subtree starts at some node of root. So try subRoot at each node: if Same Tree says yes at any node, the answer is yes. This is correct and accepted. It costs O(m · n) in the worst case, where m and n are the sizes of root and subRoot.

Recognition rule for this sub-pattern:

Visit nodes in pre/in/post order or walk two trees together node by node.

Remember this · Tree DFS

Trigger

Paths, heights, diameters, validating structure, ancestors, anything "for every subtree".

Think

If my left and right children already gave me their answers, how do I build mine?

Key question

What does my recursive function return, and what do I pass down?

Brute2Best Pro Content

Unlock Complete Visual Walkthrough & Optimal C++

The interactive animated dry-run player, optimized C++ implementation, state invariant derivations, and edge-case breakdown for this question are part of Brute2Best Pro. The anchor question of every sub-pattern is completely free.

All 440 visual dry runs & algorithms

Interactive step-by-step playback with pointer & array state transitions

52 comprehensive LLD chapters

Interactive UML diagrams, real-world stories (Food Delivery, Trading, RPG), and practice solutions

40 C++ basics labs & hardware memory models

Vtables, byte layouts, assembly insights, and multi-threading race conditions

Production-ready C++23 source code

Modern idioms, clean contracts, time/space complexity derivations, and interview takeaways

Create Free Account Log in

First anchor question per pattern, Part 1 LLD & Module 1 C++ basics are 100% Free forever.

Beyond The LeetCode Problem

How this concept connects to System Design & C++ Systems

Bridge DSA with production engineering

Top engineering interviews test whether you understand how algorithms like Tree DFS translate into production architectures and low-level memory mechanics.

LLD Architecture