LeetCode 572: Subtree of Another Tree — Recursive DFS in C++

Disclaimer

This article is an independent educational explanation of a programming problem originally published on LeetCode. The original problem statement, examples, constraints, trademarks, and related materials belong to LeetCode and their respective rights holders.

The real-world scenario is a hypothetical educational adaptation and does not represent a confirmed company process unless explicitly stated with a reliable source.

The solution, explanation, and code are for learning and reference. Other valid approaches may exist. Readers should verify current requirements on the original LeetCode page.

Article Summary

The Subtree of Another Tree problem asks whether one binary tree appears inside another binary tree as an exact rooted subtree.

The important word is exact. A valid match must have:

• The same node values
• The same left-child structure
• The same right-child structure
• No missing descendants
• No additional descendants

A clean solution combines two recursive operations:

1. Traverse every node in the main tree with depth-first search.
2. At each node, check whether the tree starting there is identical to subRoot.

This article explains how to derive that approach, why it works, how to implement it safely in C++, and why its worst-case time complexity is O(n × m).

Original Problem and Credit

This article is based on the LeetCode problem “Subtree of Another Tree.”

• Original problem: https://leetcode.com/problems/subtree-of-another-tree/description/
• Platform: LeetCode
• Original problem, examples, and constraints credit: LeetCode
• Explanation, adaptation, analysis, and commentary: Andy

Original Problem in Simple Terms

You are given the roots of two binary trees:

• root: the larger tree to search
• subRoot: the candidate tree to find

Return true when some node in root begins a subtree that is completely identical to subRoot. Otherwise, return false.

A subtree begins at one node and includes all descendants of that node. Therefore, matching only part of a branch is not enough.

The relevant constraints are:

• The root tree contains between 1 and 2000 nodes.
• The subRoot tree contains between 1 and 1000 nodes.
• Each node value is between -10^4 and 10^4.

Real-World Scenario

Imagine a hypothetical workflow-management platform that stores a large binary decision tree.

Each node contains an integer operation code:

• The left child represents one possible next branch.
• The right child represents another possible next branch.

A team also maintains a smaller approved workflow template. Before deploying the larger workflow, the platform must determine whether the approved template already appears inside it.

A workflow section is considered a match only when:

• Its starting operation code is the same.
• Every left branch is the same.
• Every right branch is the same.
• Neither workflow contains an additional operation that the other one does not contain.

This is exactly the subtree problem. The large workflow is root, and the approved template is subRoot.

Examples

Example 1: Exact Workflow Template Found

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

Output:
true

The subtree beginning at node 4 has this structure:

    4
   / \
  1   2

That structure and all node values exactly match subRoot.

Example 2: Similar Values but Different Structure

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

Output:
false

The node 4 in root appears to begin the desired structure, but the node 2 has an additional descendant, 0.

The candidate subtree is therefore not identical to subRoot. A subtree match cannot ignore extra descendants.

Mapping to the Original Problem

The ordering of the branches matters. A left child cannot be exchanged with a right child, even when the values are the same.

Solution Intuition

The problem can be separated into two smaller questions.

Question 1: Where Could the Match Begin?

A valid subtree can begin at any node in root.

Therefore, we must traverse the main tree and treat each node as a possible starting point.

A depth-first search works naturally because a binary tree is recursively defined:

• A node
• A left subtree
• A right subtree

At each node, we can check the current position first and then continue into the left and right subtrees when necessary.

Question 2: How Do We Verify a Candidate?

When a node in root is selected as a possible starting point, we must compare the entire tree rooted at that node with subRoot.

This is the Same Tree operation.

Two trees are identical when all of the following are true:

1. Their current nodes are both null, or both exist.
2. Their current node values are equal.
3. Their left subtrees are identical.
4. Their right subtrees are identical.

The null checks are essential because structure is part of the answer.

For example, these trees are not identical:

Tree A:          Tree B:

    4                4
   /                  \
  1                    1

They contain the same values, but the child positions are different.

Combining the Two Questions

The complete strategy is:

• Use isSubtree to search for a possible starting node.
• Use isSameTree to verify an exact match at that node.

This creates a useful two-layer recursive design:

Search recursion:
Try every possible subtree root.

Comparison recursion:
Verify values and structure from one possible root.

Algorithm

1. Define a helper function isSameTree(p, q).
2. If either p or q is null, return whether they are both null.
3. If both nodes exist, require:
   • p->val == q->val
   • Their left subtrees are identical.
   • Their right subtrees are identical.
4. In isSubtree(root, subRoot), return false if root is null because no candidate position remains.
5. Check whether the tree starting at the current root node is identical to subRoot.
6. If it is identical, return true immediately.
7. Otherwise, recursively search the left subtree.
8. If the left search does not find a match, recursively search the right subtree.
9. Return false only after every possible starting node has been rejected.

Why the Algorithm Works

The main invariant is:

Every call to isSubtree(current, subRoot) correctly determines whether subRoot occurs at current or anywhere below current.

At a particular node, there are only three possible places where a valid match can exist:

1. The subtree begins at the current node.
2. The subtree exists somewhere in the current node's left subtree.
3. The subtree exists somewhere in the current node's right subtree.

The algorithm checks all three possibilities.

The isSameTree helper is correct because it compares the trees node by node:

• If one node is null and the other is not, their structures differ.
• If both are null, that branch matches.
• If both exist but their values differ, the trees differ.
• If their values match, the trees are identical only when both corresponding child pairs are also identical.

Therefore, isSameTree returns true exactly when the two rooted trees have the same values and structure.

Because isSubtree tests the current node and recursively covers every node below it, it returns true exactly when an identical copy of subRoot exists inside root.

Complexity Analysis

Let:

• n be the number of nodes in root.
• m be the number of nodes in subRoot.
• h_root be the height of root.
• h_sub be the height of subRoot.

Time Complexity

The search may visit all n nodes in root.

At each visited node, isSameTree may compare as many as m nodes before finding a mismatch or confirming a match.

Therefore, the worst-case time complexity is:

O(n × m)

This worst case can occur when many nodes in root have values and structures similar to subRoot, causing repeated comparisons to continue deeply before failing.

The final result is not written as O(n + m) because nodes in subRoot may be examined repeatedly for many different candidate positions in root.

Space Complexity

The algorithm does not create an auxiliary collection such as a vector, stack, queue, or hash map. However, recursive function calls consume call-stack space.

The search recursion can use up to O(h_root) frames. While evaluating a candidate, isSameTree can add up to O(h_sub) comparison frames.

Therefore, the auxiliary space complexity is:

O(h_root + h_sub)

In the worst case, both trees can be completely skewed, so their heights are proportional to their node counts:

O(n + m)

For balanced trees, the recursion depth is closer to:

O(log n + log m)

C++ Solution: DFS with Exact Tree Comparison

/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     TreeNode* left;
 *     TreeNode* right;
 *     TreeNode() : val(0), left(nullptr), right(nullptr) {}
 *     TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
 *     TreeNode(
 *         int x,
 *         TreeNode* left,
 *         TreeNode* right
 *     ) : val(x), left(left), right(right) {}
 * };
 */

class Solution {
private:
    bool isSameTree(TreeNode* p, TreeNode* q) {
        if (p == nullptr || q == nullptr) {
            return p == q;
        }

        return p->val == q->val &&
               isSameTree(p->left, q->left) &&
               isSameTree(p->right, q->right);
    }

public:
    bool isSubtree(TreeNode* root, TreeNode* subRoot) {
        if (root == nullptr) {
            return false;
        }

        if (isSameTree(root, subRoot)) {
            return true;
        }

        return isSubtree(root->left, subRoot) ||
               isSubtree(root->right, subRoot);
    }
};

Code Explanation

The isSameTree Helper

if (p == nullptr || q == nullptr) {
    return p == q;
}

When at least one pointer is null, the two positions match only when both pointers are null.

This single condition handles three cases:

When both nodes exist, the function checks the current values and both child branches:

return p->val == q->val &&
       isSameTree(p->left, q->left) &&
       isSameTree(p->right, q->right);

C++ evaluates && from left to right and stops as soon as one condition is false.

Therefore:

• Different current values stop the comparison immediately.
• A mismatching left subtree prevents an unnecessary right-subtree comparison.
• The function returns true only when every required comparison succeeds.

The isSubtree Search

if (root == nullptr) {
    return false;
}

Reaching a null position means there are no more nodes at which a non-empty subRoot could begin.

The algorithm then tests the current node:

if (isSameTree(root, subRoot)) {
    return true;
}

When the current subtree is not identical, the search continues below it:

return isSubtree(root->left, subRoot) ||
       isSubtree(root->right, subRoot);

The || operator also short-circuits. If the left subtree contains a match, C++ returns true without searching the right subtree.

Walkthrough

Consider the second example:

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

The main tree is:

        3
       / \
      4   5
     / \
    1   2
       /
      0

The candidate tree is:

      4
     / \
    1   2

Step 1: Test the Main Root

Compare the subtree starting at 3 with the candidate starting at 4.

3 != 4

The comparison fails immediately.

Step 2: Search the Left Subtree

The search moves to node 4.

The current values match:

4 == 4

The left children also match:

1 == 1

Both node 1 branches are null, so that part is identical.

The right children have value 2, so their values also match:

2 == 2

However, the node 2 in the main tree has a left child 0, while the node 2 in subRoot has no left child.

The helper eventually compares:

0 versus null

Exactly one pointer is null, so isSameTree returns false.

Step 3: Continue Searching

The algorithm continues checking the remaining nodes in the main tree.

None of them begins a tree identical to subRoot, so the final answer is:

false

The extra node 0 cannot be ignored because a subtree includes all descendants of its starting node.

Common Mistakes

1. Comparing Only Node Values

Finding a node whose value equals subRoot->val does not prove that the entire subtree matches.

All corresponding descendants must also match.

2. Ignoring Null Positions

Null pointers encode tree structure.

The following situations must be treated differently:

Both pointers are null       -> matching structure
Only one pointer is null     -> different structure

Without these checks, trees with different shapes may incorrectly appear equal.

3. Accepting a Partial Match

A candidate is not a valid subtree when the corresponding node in root contains additional descendants.

The match must include all descendants of the selected starting node.

4. Searching Only Nodes with Different Root Values

A repeated value can appear in many positions. Even when one node with the correct value fails, another node with the same value may begin a valid match.

The traversal must continue until a complete match is found or every node has been tested.

5. Reporting O(n + m) Time

The algorithm does not compare the trees only once.

It may run an O(m) comparison at many of the n candidate nodes, producing O(n × m) time in the worst case.

6. Calling top(), Indexing, or Dereferencing Without Validation

For tree recursion, always check whether a pointer is null before reading:

node->val
node->left
node->right

The helper's null base case prevents invalid pointer access.

Key Takeaways

1. Subtree matching requires exact structure and values. A partial branch or a branch with extra descendants is not a match.
2. Separate searching from comparison. Use one recursive function to visit candidate roots and another to compare two trees.
3. Null pointers are part of the structure. Correct base cases are essential for distinguishing different tree shapes.
4. The worst-case time complexity is O(n × m). The candidate tree may be compared repeatedly at many nodes.
5. Recursive space depends on tree height. It is O(h_root + h_sub), which becomes O(n + m) for skewed trees.