AlgoMaster Logo

Subtree of Another Tree

Last Updated: March 29, 2026

easy

Understanding the Problem

We have two binary trees. We need to figure out whether subRoot appears somewhere inside root as a complete subtree. "Complete subtree" is the important phrase here. It's not enough for subRoot to match just a portion of some subtree in root. The matching subtree must include all descendants, meaning the leaf nodes must also match up.

So if root has a node with value 4 that has children 1 and 2, and subRoot is exactly that same structure (4 with children 1 and 2, both being leaves), then we have a match. But if that node 2 in root has an extra child that subRoot doesn't have, it's not a match.

The key observation is that this problem breaks down into two sub-tasks: (1) find nodes in root that could be the "starting point" of a match, and (2) verify whether the subtree rooted at that node is structurally identical to subRoot.

Key Constraints:

  • 1 <= number of nodes in root <= 2000 — The root tree is small. Even O(n^2) approaches will comfortably fit within time limits.
  • 1 <= number of nodes in subRoot <= 1000 — The subtree to match can be up to half the size of the main tree.
  • -10^4 <= node values <= 10^4 — Integer values, no overflow concerns. Values can be negative, so we need to handle that in serialization approaches.

Approach 1: DFS with Same Tree Check

Intuition

The most natural way to think about this is: visit every node in root, and at each node, ask "does the subtree rooted here look exactly like subRoot?" If we find any such node, we return true. If we exhaust the entire tree without finding a match, we return false.

Checking whether two trees are identical is a classic recursive problem on its own. Two trees are the same if their root values match, their left subtrees are the same, and their right subtrees are the same. Both being null also counts as "the same."

So the solution is really two recursive functions layered on top of each other: one that traverses root looking for potential match points, and another that verifies a match by comparing two trees node by node.

Algorithm

  1. If root is null, return false (there's no subtree to match against).
  2. Check if the tree rooted at root is identical to subRoot using a helper function.
  3. If it is, return true.
  4. Otherwise, recursively check whether subRoot is a subtree of root.left or root.right.
  5. The helper function isSameTree compares two trees: if both are null, return true. If one is null or values differ, return false. Otherwise, recursively compare left and right children.

Example Walkthrough

1Start at root (3). Call isSameTree(3, subRoot=4)
3check4125
1/5
1subRoot to find: [4, 1, 2]
412
1/5

Code

The brute force works but does redundant comparisons at every node. What if we represented each tree as a string and reduced the problem to substring matching?

Approach 2: Tree Serialization with String Matching

Intuition

Here's a different angle: what if we convert both trees into strings and then check if one string is a substring of the other? If we serialize both trees using preorder traversal, including markers for null nodes, then subRoot is a subtree of root if and only if the serialized subRoot appears as a substring within the serialized root.

The trick is in the serialization. We can't just concatenate values because that creates ambiguity. For example, a node with value "12" would look the same as a node "1" followed by "2". So we need delimiters between values and special markers for null children to preserve the tree structure.

Algorithm

  1. Serialize root into a string using preorder traversal. For each node, append a delimiter followed by the node's value. For null nodes, append a delimiter followed by a null marker (e.g., #).
  2. Serialize subRoot the same way.
  3. Check if the serialized subRoot is a substring of the serialized root.
  4. If yes, return true. Otherwise, return false.

Example Walkthrough

1Serialize root via preorder: visit 3
0
,
1
3
node 3
1/5
1Serialize subRoot via preorder: visit 4
0
,
1
4
node 4
1/5

Code

The serialization approach works well but builds large strings. What if we could fingerprint each subtree with a hash and compare in O(1) per node, without building any strings at all?

Approach 3: Tree Hashing (Merkle Hash)

Intuition

This approach borrows an idea from Merkle trees (used in Git, blockchains, and file systems). The concept is simple: assign each subtree a hash value computed from its structure. A leaf node's hash depends on its value. An internal node's hash depends on its value combined with the hashes of its left and right children. If two subtrees have the same structure and values, they'll produce the same hash.

So we compute the hash for every subtree in root and the hash for subRoot. Then we just check if subRoot's hash appears anywhere in root. Each hash computation is O(1) per node, so the total work is O(m + n).

The one subtlety is hash collisions. Two different trees could theoretically produce the same hash. To handle this, when we find a hash match, we do a final isSameTree check to confirm.

Algorithm

  1. Compute the hash of subRoot by recursively hashing its tree structure.
  2. Traverse root and compute the hash of every subtree.
  3. At each node in root, check if the subtree hash matches subRoot's hash.
  4. If a hash match is found, do a full isSameTree check to rule out hash collisions.
  5. Return true if a confirmed match is found, false otherwise.

Example Walkthrough

1Start hashing bottom-up. Compute leaf hashes first.
341h(1)2h(2)5
1/5
1Compute subRoot hash bottom-up. Start with leaves.
41h(1)2h(2)
1/5

Code