DSA sheet · Trees · DFS pattern

Subtree of Another Tree

This video takes the Same Tree check from Problem 1 and uses it as a tool inside a bigger search. We walk over every node of a big tree and ask, at each one: "does the small tree start right here?" Asking "is this the same tree?" at every node is the whole trick. The problem matters because it teaches a pattern you will see again: one recursive function that searches, calling another recursive function that checks.

Every problem below follows the same order:
① the question in simple words → ② what the constraints tell us → ③ intuition → ④ building the conditions from examples → ⑤ approach steps → ⑥ code → ⑦ code line by line → ⑧ dry run → ⑨ complexity & remember

• Part 0 · What you must know before starting
• Part A · Subtree of Another Tree with DFS
• Part B · What about BFS? (the teacher's homework)
• Part C · Revision page

Part 0 · Before starting

Words we will use

• Subtree of a node: pick any node X. X together with everything below it (its children, their children, all the way down to the leaves) is "the subtree rooted at X".
• Leaf: a node with no children.
• Height (h): the number of levels from the root down to the deepest leaf. A balanced tree with n nodes has height about log n. A tree shaped like a straight line (a skewed tree) has height n.

The tool we reuse: Same Tree

The teacher assumes you already know Same Tree (Problem 1). Here is a quick recap, because the whole solution leans on it.

def isSame(p, q):
    if p is None and q is None:   # both empty: this spot matches
        return True
    if p is None or q is None:    # only one empty: shapes differ
        return False
    if p.val != q.val:            # both exist, numbers differ
        return False
    return isSame(p.left, q.left) and isSame(p.right, q.right)

Two fingers, one on each tree, moving together. Both None → fine. One None → shapes differ. Values differ → not same. Otherwise left-with-left and right-with-right.

Part A · Subtree of Another Tree with DFS

LeetCode 572

1The question in simple words

You get two trees: a big one (root) and a small one (subRoot). Return True if the small tree appears somewhere inside the big one, with the same shape and the same values. Otherwise return False.

"Appears inside" has a strict meaning: there must be some node X in the big tree where the subtree rooted at X is exactly the same tree as subRoot. That means: once X matches the top of subRoot, every child below X must match too, all the way down. X cannot have extra nodes hanging below it.

        3
       / \
      4   5
     / \
    1   2

      4
     / \
    1   2

True: the 4 on the left of
the root, with its 1 and 2,
is exactly subRoot.

And one case that looks right but is not (this one is in the LeetCode examples):

        3
       / \
      4   5
     / \
    1   2
       /
      0

      4
     / \
    1   2

False: under the big tree's 2
there is an extra 0. The
subtree at 4 is 4-1-2-0, which
is not the same as 4-1-2.

2What the constraints tell us

• Nodes in root: 1 to 2000. Nodes in subRoot: 1 to 1000. So neither tree is ever empty at the start.
• The teacher points out that subRoot can be at most about half the size of root. Her reading: if both trees had the same size, the only way to match is that the two trees are completely equal. Otherwise the small tree must sit somewhere inside the left part or the right part of the big tree. So we expect to search down the left and right sides.
• Values: −10⁴ to 10⁴. We never add or multiply the values here, we only compare them with !=. So there's no risk of overflow and nothing to worry about.
• Sizes up to 2000 and 1000 are small. Even an O(n × m) or O(n²) answer will pass easily (we check this at the end).

3Intuition: how to think about it

Picture subRoot as a small stencil cut out of paper. You slide the stencil over the big tree, placing its top on one node at a time. At each spot you ask: "does the stencil fit exactly here?" That "fit exactly" question is just Same Tree.

• If it fits at the current node → True, stop. No need to look anywhere else.
• If it doesn't fit → move the stencil to the left child and try there, then to the right child.

Only the big tree's pointer moves during the search. subRoot stays fixed at its top. subRoot's own pointer starts moving only inside the Same Tree check, after a starting spot has been chosen.

So we need two functions:

4Building the conditions from examples

The teacher builds the logic on this example. To keep the two 4s apart, call them 4a (the upper one) and 4b (the lower one).

         3
        / \
      4a   5
     /  \
    1    4b
        /  \
       1    2

      4
     / \
    1   2

Step 1: try the root first

Put the stencil on 3. Same Tree(3, 4) fails immediately: 3 ≠ 4. So the small tree does not start at 3. It must be somewhere in 3's left part or 3's right part.

Step 2: the root failed, so move only the big tree's pointer

Go to 3's left child, 4a. We change root to root.left, but subRoot stays at its top (4). Why? Because we haven't matched anything yet. We are still looking for a place to start, so the stencil's top must be compared again from the beginning.

Step 3: 4a matches the top, so now run the full Same Tree check

4a = 4, so this spot looks promising. Now Same Tree takes over, and here both pointers move together:

• Left with left: 4a's left is 1, subRoot's left is 1 → equal ✓ (and both have no children → fine).
• Right with right: 4a's right is 4b, subRoot's right is 2 → 4 ≠ 2 ✗.

So the check started at 4a fails. Matching the top is not enough. Every node below must match too.

Step 4: keep searching below 4a

Back in the search. Try 4a's left child, 1: Same Tree(1, 4) fails at once (1 ≠ 4). Try 4a's right child, 4b: 4 = 4 ✓, left 1 = 1 ✓, right 2 = 2 ✓, and all their children are None on both sides ✓. Same Tree is True.

Step 5: found it, so stop and don't look at the right side

We found the small tree in the left part of 3. Is there any reason to visit 5 now? No. One match is enough. So the search should return True as soon as either side says True. That means we join the left search and the right search with or.

Rule: check the current node before going down

Suppose the big tree's root itself were 4 with children 1 and 2. Same Tree(root, subRoot) would be True right away. Why go left or right at all? So the very first thing the search does (after the base case) is: if isSame(root, subRoot): return True.

The base case: what if the big tree's pointer becomes None?

The teacher compares two situations:

The constraints say subRoot always has at least one node, and the search never changes subRoot. So the second row never happens. We only need the first: if root is None: return False.

Example 3: watching the base case fire

The teacher changes Example 1: suppose 4b has no children.

         3
        / \
      4a   5
     /  \
    1    4b        ← no children now
                   subRoot is still 4 → (1, 2)

• At 4a: 4 = 4, 1 = 1, but 4b ≠ 2 → not same.
• At 1: 1 ≠ 4 → not same.
• At 4b: 4 = 4 ✓, but 4b's left is None while subRoot's left is 1 → only one is None → not same. 4b looks like the top of subRoot, but its children are missing.
• Now the search goes into 4b's children, which are None. Here isSubtree(None, subRoot) runs. The base case returns False. This is the moment the base case is needed, even though the original root was not empty.
• Back up, try 5: 5 ≠ 4. Its children are None → base case → False.
• Final answer: False ✓

Inside Same Tree: why each rule, in this problem

The teacher walks through Same Tree again, using the names root and subRoot:

• Both None → True: both fingers have gone off the bottom of the tree at the same spot (below a leaf on both sides). Nothing is missing.
• Exactly one None → False: we already know they are not both None, so if either one is None, one tree has a node where the other has none.
• Values differ → False: if the two "parents" don't match, there's no point checking their children. In Example 1, Same Tree(3, 4) stops right here.
• Otherwise → left-left AND right-right: at 4a, the left side (1 vs 1) says True, but the right side (4b vs 2) says False. True and False is False. One side matching is not enough for "same".

5Approach steps

1. isSubtree(root, subRoot): if root is None → return False.
2. If isSame(root, subRoot) is True → return True (found it right here).
3. Otherwise search the left part, then the right part, keeping subRoot the same. Return True if either finds it.
4. isSame(p, q): both None → True. One None → False. Values differ → False. Else return left-left and right-right.

6Code (Python)

class Solution:
    def isSubtree(self, root, subRoot):
        if root is None:                          # walked off the big tree
            return False
        if self.isSame(root, subRoot):            # does it start right here?
            return True
        # not here: search left, then right; subRoot does NOT move
        return self.isSubtree(root.left, subRoot) or self.isSubtree(root.right, subRoot)

    def isSame(self, p, q):
        if p is None and q is None:               # both empty
            return True
        if p is None or q is None:                # only one empty
            return False
        if p.val != q.val:                        # values differ
            return False
        return self.isSame(p.left, q.left) and self.isSame(p.right, q.right)

7Code line by line

8Dry run using the call stack

Example 1 again (4a on top, 4b below it). "S" = isSubtree, "same" = isSame.

1. S(3): 3 isn't None. same(3, 4) → 3 ≠ 4 → False. So go left. S(3) waits.
2. S(4a): same(4a, 4): 4 = 4 ✓ → same(1, 1): equal, children (N,N) and (N,N) → True. Then same(4b, 2): 4 ≠ 2 → False. True and False → same(4a, 4) is False. S(4a) goes left and waits.
3. S(1): same(1, 4) → 1 ≠ 4 → False. Go left: S(None) → base case False. Go right: S(None) → False. False or False → S(1) returns False.
4. Back in S(4a): left said False, so or runs the right side: S(4b).
5. S(4b): same(4b, 4): 4 = 4 ✓, same(1, 1) ✓, same(2, 2) ✓ → True. S(4b) returns True right away, without going into its children.
6. S(4a) gets True from its right side → returns True.
7. S(3) gets True from its left side → or never calls S(5). Final answer: True ✓

The newest call is on top (red). Notice that a Same Tree check sits on top of the search calls while it runs. Both kinds of call use the stack at the same time.

9Complexity & remember

Time: the teacher calls it O(n²)

For every node of the big tree, we may run a Same Tree check that walks a big part of subRoot before it fails. The teacher's worst case makes this clear: all values are 1, except one 2 at the very bottom of subRoot.

1
 \
  1
   \
    1
     \
      1
       \
        1  ...

1
 \
  1
   \
    2

Start at the first 1: 1 = 1, 1 = 1, then 1 vs 2 fails. Go back and start at the next 1: again 1, 1, then fail. And again… At every starting node we walk almost all of subRoot before we find the mismatch. So the work is about (nodes in root) × (nodes in subRoot).

• The more exact name is O(n × m), where n = nodes in root and m = nodes in subRoot. The teacher just calls it n².
• Is it fast enough? With n = 2000, she computes n² = 4 × 10⁶ (and n × m = 2 × 10⁶). Both are far below the ~10⁸ limit for TLE. Fine.

Space

• The search uses a call stack as tall as the big tree: about log n if balanced, n if skewed.
• While a Same Tree check runs, it adds its own stack on top, as tall as the smaller tree.
• The teacher adds them: about 2 × log n for balanced trees, 2n for skewed ones. Dropping the 2, that's O(h): O(log n) balanced, O(n) worst case.

Part B · What about BFS?

The teacher doesn't code BFS here. She says it can be done, but she prefers DFS, and she leaves BFS to you as homework. Here's her reasoning, and then a working version so you can check your homework.

1Why the teacher prefers DFS here

• The logic is naturally "check this node, then go left, then go right". That is exactly how DFS moves, so the recursive code is short and reads like the idea.
• With BFS you would need to keep extra things in the queue together with each node (she mentions storing pairs). That makes the code a bit messy.
• Time and space are about the same either way. In BFS the queue takes the space instead of the call stack. She says the space comes to about 2n in BFS (queue plus the checks), so O(n).
• For Same Tree itself, both BFS and DFS versions were covered in Problem 1, so you can use either one as the "check".

2Approach steps

1. Put the big tree's root in a queue (the constraints promise it exists).
2. While the queue isn't empty: pop one node.
3. If isSame(node, subRoot) → return True.
4. Otherwise push its left and right children (only the ones that exist).
5. If the queue runs out → no starting spot worked → return False.

3Code (Python)

from collections import deque

class Solution:
    def isSubtree(self, root, subRoot):
        queue = deque([root])
        while queue:
            node = queue.popleft()
            if self.isSame(node, subRoot):     # try this node as the start
                return True
            if node.left:
                queue.append(node.left)
            if node.right:
                queue.append(node.right)
        return False

    def isSame(self, p, q):                    # same check as Part A
        if p is None and q is None:
            return True
        if p is None or q is None:
            return False
        if p.val != q.val:
            return False
        return self.isSame(p.left, q.left) and self.isSame(p.right, q.right)

4Dry run: watch the queue

Example 1. Yellow = the node popped at this step.

Notice the difference from DFS: BFS checked 5 (step 3) before reaching 4b, because 5 is on a higher level. DFS never touched 5. Here DFS did less work, which matches the teacher's preference.

5Complexity

• Time O(n × m): still one Same Tree check per big-tree node.
• Space O(n): the queue can hold a whole level (up to about n/2 nodes), plus the Same Tree stack.

Part C · Revision page

root = TreeNode(3, TreeNode(4, TreeNode(1), TreeNode(4, TreeNode(1), TreeNode(2))), TreeNode(5))
sub  = TreeNode(4, TreeNode(1), TreeNode(2))
root2 = TreeNode(3, TreeNode(4, TreeNode(1), TreeNode(2, TreeNode(0))), TreeNode(5))
root3 = TreeNode(3, TreeNode(4, TreeNode(1), TreeNode(4)), TreeNode(5))

s = Solution()
print(s.isSubtree(root, sub))    # True  (found at the lower 4)
print(s.isSubtree(root2, sub))   # False (extra 0 under the 2)
print(s.isSubtree(root3, sub))   # False (lower 4 has no children)

Based on this video: Subtree of Another Tree | DFS