Subtree of Another Tree

Easytreedepth-first-searchrecursion
Category: Trees
Companies that ask this question:
AmazonFacebookGoogleMicrosoft
LeetCode →NeetCode →

Approach

Subtree of Another Tree

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

Example 1

Input: root = [3,4,5,1,2], subRoot = [4,1,2]
Output: true

Tree root:        subRoot:
      3              4
     / \            / \
    4   5          1   2
   / \
  1   2

Subtree starting at node 4 matches subRoot

Example 2

Input: root = [3,4,5,1,2,null,null,null,null,0], subRoot = [4,1,2]
Output: false

Tree root:        subRoot:
      3              4
     / \            / \
    4   5          1   2
   / \
  1   2
     /
    0

Node 4 has extra child (0), so not a match

Example 3

Input: root = [1,1], subRoot = [1]
Output: true

Intuition

We need to check if subRoot appears as an exact subtree anywhere in root.

Strategy:

  1. Traverse every node in root
  2. At each node, check if the tree rooted there equals subRoot
  3. Use the "Same Tree" check from previous problem

This combines two problems:

  • Tree traversal (to visit all potential starting points)
  • Tree comparison (to check if subtrees match)

Pattern Recognition

This is a Tree Traversal + Tree Comparison problem with:

  • DFS to visit all nodes in main tree
  • Recursive comparison at each potential starting point
  • Reuse "Same Tree" logic as helper function

Approach

Two-Function Solution

Function 1: isSubtree(root, subRoot)

  • Traverse all nodes in root
  • At each node, check if it matches subRoot
  • Use DFS to explore all nodes

Function 2: isSameTree(p, q)

  • Check if two trees are identical
  • Same logic as "Same Tree" problem

Algorithm:

isSubtree(root, subRoot):
  if not root: return False
  if isSameTree(root, subRoot): return True
  return isSubtree(root.left, subRoot) or isSubtree(root.right, subRoot)

isSameTree(p, q):
  if not p and not q: return True
  if not p or not q: return False
  if p.val != q.val: return False
  return isSameTree(p.left, q.left) and isSameTree(p.right, q.right)

Why this works:

  • We check every possible starting point in root
  • isSameTree ensures exact match (structure + values)
  • DFS guarantees we don't miss any potential subtree

Edge Cases

  • subRoot is null → typically return True (null is subtree of everything)
  • root is null, subRoot not null → return False
  • subRoot equals entire root tree
  • subRoot matches a leaf
  • Multiple nodes with same value as subRoot.val
  • subRoot appears multiple times but only one exact match

Complexity Analysis

  • Time: O(n × m) where n = nodes in root, m = nodes in subRoot

    • Visit all n nodes in root (outer traversal)
    • At each node, potentially compare m nodes (isSameTree)
    • Worst case: O(n × m)
    • Average case: Much better with early termination

  • Space: O(h₁ + h₂) where h₁, h₂ = heights

    • Recursion stack for both functions
    • O(log n) for balanced trees
    • O(n) for skewed trees

Solution

java
1class TreeNode {
2    int val;
3    TreeNode left;
4    TreeNode right;
5    TreeNode() {}
6    TreeNode(int val) { this.val = val; }
7    TreeNode(int val, TreeNode left, TreeNode right) {
8        this.val = val;
9        this.left = left;
10        this.right = right;
11    }
12}
13
14class Solution {
15    public boolean isSubtree(TreeNode root, TreeNode subRoot) {
16        // If subRoot is null, it's a subtree of any tree
17        if (subRoot == null) {
18            return true;
19        }
20
21        // If root is null but subRoot is not, can't be a subtree
22        if (root == null) {
23            return false;
24        }
25
26        // Check if trees rooted at current node are the same
27        if (isSameTree(root, subRoot)) {
28            return true;
29        }
30
31        // Otherwise, check left and right subtrees
32        return isSubtree(root.left, subRoot) || isSubtree(root.right, subRoot);
33    }
34
35    private boolean isSameTree(TreeNode p, TreeNode q) {
36        // Both null - same
37        if (p == null && q == null) {
38            return true;
39        }
40
41        // One null, one not - different
42        if (p == null || q == null) {
43            return false;
44        }
45
46        // Different values - different
47        if (p.val != q.val) {
48            return false;
49        }
50
51        // Check both subtrees
52        return isSameTree(p.left, q.left) && isSameTree(p.right, q.right);
53    }
54}
55
Loading visualizer...