ToolMight LogoToolMight
EasyTrees & BSTPattern: Tree Traversal DFSPattern: Same Tree Equality Check

Subtree of Another Tree

Determine if a binary tree contains a subtree identical in structure and node values to another tree. Learn how to combine outer tree DFS traversal with inner tree isomorphism matching.

Problem Statement

Given the roots of two binary trees root and subRoot, return true if there is a subtree of root with the same structure and node values of subRoot and false otherwise.

A subtree of a binary tree tree is a tree that consists of a node in tree and all of this node's descendants. The tree tree could also be considered as a subtree of itself.

Examples & Constraints

Example 1
Input: root = [3, 4, 5, 1, 2], subRoot = [4, 1, 2]
Output: true
Explanation: The left child of node 3 has root 4 with left child 1 and right child 2, which matches subRoot exactly.
Example 2
Input: root = [3, 4, 5, 1, 2, null, null, null, null, 0], subRoot = [4, 1, 2]
Output: false
Explanation: Although node 4 has children 1 and 2, node 2 additionally has a child 0 in root, making the trees non-identical.
Constraints
  • The number of nodes in the root tree is in the range [1, 2000].
  • The number of nodes in the subRoot tree is in the range [1, 1000].
  • -10^4 <= root.val <= 10^4
  • -10^4 <= subRoot.val <= 10^4

Double Recursive DFS (Traversal + Equality)

Optimal Approach
Time:O(n * m)
Space:O(h)

Traverse every candidate node in root with DFS. At each node, check if the subtree rooted there is strictly identical (isSameTree) to subRoot in structure and node values.

Time ComplexityO(n * m)

Where N is the number of nodes in root and M is the number of nodes in subRoot. In the worst case (e.g. repeated identical values), isSameTree is called for every node in root.

Space ComplexityO(h)

Consumes memory on the call stack proportional to the height H of root (at most O(n) for a skewed tree, O(log n) for a balanced tree).

Underlying algorithmic logic

The Two-Level Recursive Strategy

This problem requires two distinct recursive functions working in tandem:

  1. Helper Function: `isSameTree(s, t)`:
  • Compares if two trees are completely isomorphic (identical structure and values):
  • If both s == null and t == null, return true (both empty).
  • If only one is null, or if s.val != t.val, return false.
  • Recurse: isSameTree(s.left, t.left) && isSameTree(s.right, t.right).
  1. Main Function: `isSubtree(root, subRoot)`:
  • If subRoot == null, an empty tree is trivially a subtree of any tree; return true.
  • If root == null, an empty main tree cannot contain a non-empty subRoot; return false.
  • If isSameTree(root, subRoot) is true, we found a match! Return true.
  • Otherwise, check if subRoot matches anywhere in the left subtree OR right subtree: isSubtree(root.left, subRoot) || isSubtree(root.right, subRoot).

Strict Subtree Invariant: No Stray Descendants

A common mistake is returning true if subRoot is a subset of root. The definition requires the subtree to include all of the candidate node's descendants. The isSameTree equality check ensures that if subRoot has null children, the matched candidate must also have null children at those exact positions.

Step-by-step execution walkthrough

1
Inspect root (3)

Compare tree at 3 with subRoot (4). 3 != 4 -> isSameTree fails. Recurse into children of 3.

isSubtree(3.left, subRoot) || isSubtree(3.right, subRoot)
2
Inspect root.left (4)

Check isSameTree(4, 4): root values match (4 == 4). Compare left children: 1 == 1. Compare right children: 2 == 2.

isSameTree(4, 4) -> true!
3
Result Propagation

Match confirmed at node 4. Return true up the call stack to root.

Result: true
Advantages
  • •Clean and modular recursion pattern
  • •Separates traversal from structural isomorphism logic
Trade-offs
  • •Worst-case O(n * m) time on trees with heavily repeated values

Code Implementations

Copy & paste production-ready solutions for Double Recursive DFS (Traversal + Equality) in your language of choice

File: solution.py
Python
class TreeNode:
    def __init__(self, val=0, left=None, right=None):
        self.val = val
        self.left = left
        self.right = right
def is_same_tree(s: TreeNode | None, t: TreeNode | None) -> bool:
    if not s and not t:
        return True
    if not s or not t or s.val != t.val:
        return False
    return is_same_tree(s.left, t.left) and is_same_tree(s.right, t.right)
def is_subtree(root: TreeNode | None, sub_root: TreeNode | None) -> bool:
    if not sub_root:
        return True
    if not root:
        return False
    if is_same_tree(root, sub_root):
        return True
    return is_subtree(root.left, sub_root) or is_subtree(root.right, sub_root)
if __name__ == "__main__":
    # root: [3, 4, 5, 1, 2]
    root = TreeNode(3)
    root.left = TreeNode(4, TreeNode(1), TreeNode(2))
    root.right = TreeNode(5)
    # subRoot: [4, 1, 2]
    sub_root = TreeNode(4, TreeNode(1), TreeNode(2))
    print("Is Subtree:", is_subtree(root, sub_root))
Interactive visualizer available

Understand Binary Search Tree Visually

Explore hierarchical parent-child nodes, traversal modes (in-order, pre-order, post-order), and search lookups. Test live edge cases and watch memory state transitions step-by-step.

Launch Binary Search Tree Visualizer

Frequently Asked Questions

Related Logic & Algorithm Problems

All problems
EasyTrees & BST
Visualizer

Maximum Depth of Binary Tree

Find the maximum depth (height) of a binary tree along the longest path from root to leaf. The quintessential problem for learning bottom-up divide-and-conquer tree recursion.

1 approach(O(n))
Learn logic
EasyTrees & BST
Visualizer

Invert Binary Tree

Mirror-flip a binary tree so every left subtree swaps with the right subtree. The quintessential problem for mastering tree recursion and depth-first traversal.

1 approach(O(n))
Learn logic
MediumTrees & BST
Visualizer

Binary Tree Level Order Traversal

Return the level order traversal of a binary tree's node values from left to right, level by level. The premier problem for learning FIFO queue BFS level snapshots.

1 approach(O(n))
Learn logic