Subtree of Another Tree

Table of Contents +

Subtree of Another Tree builds on a smaller question. You take the Same Tree check you already know. Then you apply it again and again. The interviewer wants to see if you can reuse a solved problem to solve a bigger one.

🎯 The Problem

You get a big tree, call it the root. You get a small tree, call it the subRoot. A binary tree is a structure where each node has a value and up to two children. Say if the small tree appears inside the big tree exactly.

The rules:

  • Look for a node in the big tree where the tree below it matches subRoot.
  • The match must be the whole subtree: same shape and same values.
  • Not just the values appearing somewhere. All of it, starting at that node.
  • Return true if any such node exists.
Input:
   root            subRoot
     3                4
    / \             / \
   4   5           1   2
  / \
 1   2


Output: true


Explanation: The subtree starting at node 4 in root matches subRoot exactly.

Here is the big tree with the matching part. The subtree at node 4 is what we are looking for.

3

4

5

1

2

🐢 Approach 1: Same Tree Check At Every Node (Brute Force)

The idea in one line: walk every node in the big tree and ask if the small tree matches starting right there.

The idea:

  • Reuse the Same Tree check you already know.
  • It returns true when two trees are identical. Identical means same shape and same values everywhere.
  • A subtree match means: some node where the tree below it is identical to the small tree.

How it works:

  • Walk every node in the big tree.
  • At each node, call the Same Tree check against subRoot.
  • If any node gives a full match, return true.

Why it is weak:

  • At each of the n big-tree nodes you may run a full compare costing up to m steps.
  • So the worst case is about O(n times m).
  • The same compares can repeat from nearby nodes.

Here is the check-at-every-node code:

subtree_same_tree_each_node.py
def is_subtree(root, sub_root):
    def same(a, b):
        if not a or not b: return a is b
        return a.val == b.val and same(a.left, b.left) and same(a.right, b.right)
    if not root: return False
    return same(root, sub_root) or is_subtree(root.left, sub_root) or is_subtree(root.right, sub_root)

⚡ Approach 2: String Serialization Plus Search (Better)

The idea in one line: turn each tree into one text string, then search for the small string inside the big one.

The idea:

  • Serialize a tree means turn it into a single line of text, with markers for empty spots.
  • A subtree match becomes a substring match between the two strings.

How it works:

  • Serialize the big tree and the small tree.
  • Search for the small string inside the big string.
  • A careful string search can reach near O(n plus m).

Why it is tricky:

  • You must add empty markers and value separators or false matches creep in.
  • Edge cases break it easily.
  • In an interview the same-tree-at-every-node version is the safer, clearer pick.

The diagram below shows how the walk tries the same-tree check at each node until it finds a match.

not same

same as subRoot

check node 3

check node 4

return true

check node 5

Steps to Solve

  1. Write a helper isSame(a, b) that returns true when two trees are identical.
  2. If subRoot is empty, it always matches, so return true.
  3. If root is empty but subRoot is not, return false.
  4. At the current root node, call isSame(root, subRoot). If true, return true.
  5. Otherwise, search the left side and the right side of root.
  6. Return true if either side contains the subtree.

This Python version uses a small class and two functions, one to compare and one to search.

subtree.py
class Node:
    def __init__(self, val):
        self.val = val
        self.left = None
        self.right = None




def is_same(a, b):
    if a is None and b is None:
        return True
    if a is None or b is None:
        return False
    if a.val != b.val:
        return False
    return is_same(a.left, b.left) and is_same(a.right, b.right)




def is_subtree(root, sub_root):
    if sub_root is None:                 # empty tree fits anywhere
        return True
    if root is None:                     # nothing left to search
        return False
    if is_same(root, sub_root):          # match starting here
        return True
    return is_subtree(root.left, sub_root) or \
        is_subtree(root.right, sub_root)  # search both sides




root = Node(3)
root.left = Node(4)
root.right = Node(5)
root.left.left = Node(1)
root.left.right = Node(2)


sub_root = Node(4)
sub_root.left = Node(1)
sub_root.right = Node(2)


print(is_subtree(root, sub_root))

The output of the above code will be:

True

Let us walk through the Python version line by line so you see why each piece is there.

The is_same function is the Same Tree check. It returns true when two trees match in shape and values everywhere. We reuse it as a building block. This is the heart of the trick: solve the smaller problem once, then call it many times.

Inside is_subtree, the first line is if sub_root is None: return True. An empty tree fits inside any tree. So this is a safe yes.

Next is if root is None: return False. We ran out of big tree but the small tree still has nodes. So there is nowhere left for it to match. We say no.

Then if is_same(root, sub_root): return True. Here we ask the key question at the current node. If the tree starting right here is identical to the small tree, we are done.

Finally return is_subtree(root.left, sub_root) or is_subtree(root.right, sub_root). The current node was not a match. So we look in the left side, then the right side. The or means a match on either side counts as a yes.

⏱️ Time and Space Complexity

The search walks every node of the big tree, which is n nodes. At each node it may run a full compare that costs up to m steps, where m is the size of the small tree. So the time is O(n times m) in the worst case. The space is the recursion depth, which is O(h) where h is the height of the big tree.

Approach Time Complexity Space Complexity
Same-tree check at every node O(n × m) O(h)
String serialization plus search O(n + m) O(n + m)

Tip

This problem is really two problems in one. If you can write the Same Tree check cleanly, the rest is just calling it at every node. Solve the small piece first.

🧩 Key Takeaways

  • ✅ A subtree match means some node where the tree below is identical to the small tree.
  • ✅ Reuse the Same Tree check as a helper, then call it at every node.
  • ✅ An empty small tree always matches, so handle that case first.
  • ✅ The worst case time is O(n times m), big tree size times small tree size.
  • ✅ Solving the smaller problem first makes the bigger one easy.

Check Your Knowledge

 4 questions Show quiz Hide quiz

Test what you learned. Pick an answer for each question, then click Check.

  1. 1

    What does it mean for one tree to be a subtree of another?

    Why: A subtree match needs a node where the entire tree below it matches the small tree in shape and values.

  2. 2

    Which earlier problem do we reuse as a helper here?

    Why: We reuse the Same Tree check to test whether the tree at each node matches the small tree.

  3. 3

    Why does an empty subRoot return true right away?

    Why: An empty tree is trivially contained in any tree, so the answer is true.

  4. 4

    What is the worst-case time complexity of the two-function approach?

    Why: We may run a full compare costing m at each of the n nodes, giving O(n × m).

Score: 0 / 4

🚀 What’s Next?

Previous Same Tree Next Diameter of Binary Tree