DSA With AI
Week 4 ยท Trees

Subtree of Another Tree

Decide whether subRoot appears inside root as a subtree with identical structure and values.

Easy Trees Week 4 Practice runner

Frame the problem

  • The matching subtree must include all descendants from its chosen root.
  • Repeated values are possible.
  • An empty subRoot is usually considered a subtree.
1. Reveal example inputs and outputs

Example 1

Input:

is_subtree([
  3,
  [
    4,
    [
      1,
      null,
      null
    ],
    [
      2,
      null,
      null
    ]
  ],
  [
    5,
    null,
    null
  ]
], [
  4,
  [
    1,
    null,
    null
  ],
  [
    2,
    null,
    null
  ]
])

Output:

true

Example 2

Input:

is_subtree([
  3,
  [
    4,
    [
      1,
      null,
      null
    ],
    [
      2,
      [
        0,
        null,
        null
      ],
      null
    ]
  ],
  [
    5,
    null,
    null
  ]
], [
  4,
  [
    1,
    null,
    null
  ],
  [
    2,
    null,
    null
  ]
])

Output:

false
2. Brute force first

At every node in root, what expensive check could you run against subRoot?

3. Reveal the insight ladder
  1. Use Same Tree as the exact-match helper.
  2. If the current root matches subRoot, return True.
  3. Otherwise, recurse into the left and right children as candidate starts.
  4. A missing root cannot contain a non-empty subRoot.
4. Dry run before code
  1. root has a node 4 with children 1 and 2.
  2. subRoot is 4 with children 1 and 2.
  3. Same Tree succeeds at that candidate node.
  4. The answer is True without scanning the rest.
5. Reveal final Python solution 
def is_subtree(root, sub_root):
    if sub_root is None:
        return True
    if root is None:
        return False
    return (
        is_same_tree(root, sub_root)
        or is_subtree(root[1], sub_root)
        or is_subtree(root[2], sub_root)
    )

Complexity: Naive time is O(n * m) in the worst case, where n is root size and m is subRoot size. Space is O(h) recursion depth.

Interview narration

  • I will separate candidate search from exact matching.
  • Repeated values mean a value match alone is not enough.
  • The exact-match helper must compare structure and values all the way down.

Common traps

  • Returning True on matching root values only.
  • Forgetting near matches that fail deep in the subtree.
  • Ignoring repeated values that create multiple candidate roots.

Follow-up drills

1. How can this be optimized?

Serialize both trees with null markers and run substring search, or use tree hashing. Null markers are required to avoid shape collisions.

2. Why are null markers important in serialization?

Without null markers, different tree shapes can produce the same value sequence, so a false subtree match becomes possible.

3. What should happen when subRoot is None?

Most definitions treat the empty tree as a subtree of any tree, so return True. Clarify if the interviewer uses a different convention.

Interactive runner

Write the required Python function. Your code runs locally in this browser. Hints reveal one failing case at a time.