Subtree of Another Tree

Subtree of Another Tree

What is this problem about?

In the "Subtree of Another Tree" problem, you are given two binary trees: root and subRoot. You need to determine if subRoot is a subtree of root. A subtree of a tree T is a tree S consisting of a node in T and all of its descendants in T. Crucially, the subtree must match exactly—not just in structure, but in all node values, and it must go all the way to the leaf nodes.

Why is this asked in interviews?

This is a classic recursion problem frequently asked by Google, Bloomberg, and Amazon. it evaluates a candidate's understanding of tree traversal (specifically Depth-First Search) and their ability to solve a nested recursive problem. To solve it, you have to recursively check every node in the main tree to see if the tree starting at that node is identical to the given subRoot.

Algorithmic pattern used

The pattern used is "Nested Recursion" or "Double DFS." One recursive function (let's call it isSubtree) traverses the main tree. For every node it visits, it calls a second recursive helper function (let's call it isSameTree). isSameTree checks if two trees are identical by comparing their root values and then recursively checking their left and right subtrees.

Example explanation

Imagine Tree A has a root 3, with children 4 and 5. Node 4 has children 1 and 2. Tree B has a root 4, with children 1 and 2. To check if B is a subtree of A:

1. Compare root of A (3) with root of B (4). They don't match.
2. Move to A's left child (4). Compare this node with B. Since both are 4 and their children (1 and 2) match exactly, B is a subtree of A. If Tree A's node 2 had an extra child (e.g., node 0), then B would not be a subtree, because B's version of node 4 doesn't have that child.

Common mistakes candidates make

1. Matching only values: Thinking that if the values match, it's a subtree. You must check the entire structure below that node.
2. Stopping too early: If the roots don't match, you must continue checking the left and right children of the main tree.
3. Incomplete equality check: Forgetting to check if both trees reach null at the same time. If one tree has a child and the other doesn't, they are not the same.

Interview preparation tip

Mastering the "Is Same Tree" problem is the prerequisite for this one. Once you can confidently write a recursive function to check if two trees are identical, "Subtree of Another Tree" becomes a simple matter of applying that check at every node of a larger tree. Practice visualizing recursive calls as a stack to avoid confusion.