LeetCode 572 - Subtree of Another Tree

This problem asks us to determine whether one binary tree appears as an exact subtree inside another binary tree.

leetcodeeasytreedepth-first-searchstring-matchingbinary-treehash-function

LeetCode Problem 572

Difficulty: 🟢 Easy
Topics: Tree, Depth-First Search, String Matching, Binary Tree, Hash Function

Solution

LeetCode 572 - Subtree of Another Tree

Problem Understanding

This problem asks us to determine whether one binary tree appears as an exact subtree inside another binary tree.

We are given two binary trees:

  • root, the main tree
  • subRoot, the candidate subtree

We must return true if there exists some node inside root such that the entire tree rooted at that node is structurally identical to subRoot. Structural identity means:

  • Every corresponding node has the same value
  • The left subtrees match exactly
  • The right subtrees match exactly
  • Missing children must also match

A subtree is not just a partial match of values. The entire shape and every descendant must match perfectly.

For example:

root:
        3
       / \
      4   5
     / \
    1   2

subRoot:
      4
     / \
    1   2

The subtree rooted at node 4 inside root matches subRoot, so the answer is true.

The constraints are relatively small:

  • root has at most 2000 nodes
  • subRoot has at most 1000 nodes

These limits allow recursive depth first search solutions without requiring advanced optimization techniques.

There are several important edge cases to consider:

  • The subtree may appear deep inside the main tree
  • Trees may contain duplicate values, so matching only root values is not enough
  • A partial structural match must still return false
  • A node value match does not guarantee subtree equality
  • One extra or missing child invalidates the subtree match

The problem guarantees both trees contain at least one node.

Approaches

Brute Force Approach

The brute force solution checks every node in root as a possible starting point for the subtree.

For each node in root:

  1. Compare the subtree rooted at that node with subRoot
  2. If they are identical, return true
  3. Otherwise continue searching

To compare two trees, we recursively verify:

  • Current node values match
  • Left subtrees match
  • Right subtrees match

This approach is correct because every possible subtree root is examined.

However, it can be inefficient because for every node in root, we may perform a full subtree comparison against subRoot.

If:

  • N = number of nodes in root
  • M = number of nodes in subRoot

then in the worst case we may perform M work for each of the N nodes.

This gives a worst case time complexity of O(N × M).

Optimal DFS Matching Approach

The standard optimal solution still uses DFS, but structures the recursion carefully to minimize unnecessary work and keep the implementation elegant.

The key insight is that subtree matching naturally decomposes into two recursive operations:

  1. Search through root for potential starting positions
  2. Check whether two trees are identical

The algorithm works because subtree equality is itself recursively defined.

At every node in root:

  • If the current trees match exactly, return true
  • Otherwise recursively search the left subtree
  • Then recursively search the right subtree

This depth first traversal ensures every possible subtree location is checked exactly once.

Although the theoretical worst case remains O(N × M), this solution is efficient enough for the given constraints and is the standard accepted approach.

Approach Comparison

Approach Time Complexity Space Complexity Notes
Brute Force O(N × M) O(H) Compare subRoot against every node manually
Optimal DFS O(N × M) O(H) Recursive subtree matching with cleaner DFS structure

Here:

  • N is the number of nodes in root
  • M is the number of nodes in subRoot
  • H is the recursion depth of the tree

Algorithm Walkthrough

Step 1: Create a helper function to compare two trees

We define a function isSameTree(node1, node2).

This function determines whether two trees are completely identical.

The rules are:

  1. If both nodes are None, the trees match at this branch
  2. If only one node is None, the trees differ
  3. If node values differ, the trees differ
  4. Otherwise recursively compare:
  • left children
  • right children

This helper function gives us exact subtree equality checking.

Step 2: Traverse the main tree

We recursively traverse every node in root.

Each node is treated as a possible subtree root.

Step 3: Attempt subtree matching

At every node:

  1. Call isSameTree(currentNode, subRoot)
  2. If it returns true, we found a matching subtree
  3. Immediately return true

If the current node does not match:

  1. Search the left subtree
  2. Search the right subtree

If either side returns true, propagate the result upward.

Step 5: Return false if no match exists

If the DFS finishes without finding a matching subtree, return false.

Why it works

The algorithm works because every node in root is considered as a potential subtree root. For each candidate node, isSameTree guarantees structural and value equality through recursive comparison. Since every possible subtree position is checked exactly once, the algorithm cannot miss a valid subtree.

Python Solution

# Definition for a binary tree node.
# class TreeNode:
#     def __init__(self, val=0, left=None, right=None):
#         self.val = val
#         self.left = left
#         self.right = right

from typing import Optional

class Solution:
    def isSubtree(
        self,
        root: Optional[TreeNode],
        subRoot: Optional[TreeNode]
    ) -> bool:

        def isSameTree(
            node1: Optional[TreeNode],
            node2: Optional[TreeNode]
        ) -> bool:

            if not node1 and not node2:
                return True

            if not node1 or not node2:
                return False

            if node1.val != node2.val:
                return False

            return (
                isSameTree(node1.left, node2.left)
                and
                isSameTree(node1.right, node2.right)
            )

        if not root:
            return False

        if isSameTree(root, subRoot):
            return True

        return (
            self.isSubtree(root.left, subRoot)
            or
            self.isSubtree(root.right, subRoot)
        )

The implementation is divided into two recursive responsibilities.

The helper function isSameTree performs exact tree equality checking. It first handles base cases involving None nodes. If both nodes are missing, that branch matches successfully. If only one node exists, the structures differ. The function then compares node values and recursively checks both subtrees.

The main isSubtree function performs DFS traversal across the main tree. At each node, it first attempts a full subtree comparison using isSameTree. If a match is found, it immediately returns True.

If the current node does not match, recursion continues into the left and right children. This guarantees that every possible subtree location is examined.

The recursive structure keeps the implementation concise and directly aligned with the mathematical definition of subtree equality.

Go Solution

/**
 * Definition for a binary tree node.
 * type TreeNode struct {
 *     Val int
 *     Left *TreeNode
 *     Right *TreeNode
 * }
 */

func isSubtree(root *TreeNode, subRoot *TreeNode) bool {

    var isSameTree func(node1 *TreeNode, node2 *TreeNode) bool

    isSameTree = func(node1 *TreeNode, node2 *TreeNode) bool {

        if node1 == nil && node2 == nil {
            return true
        }

        if node1 == nil || node2 == nil {
            return false
        }

        if node1.Val != node2.Val {
            return false
        }

        return isSameTree(node1.Left, node2.Left) &&
            isSameTree(node1.Right, node2.Right)
    }

    if root == nil {
        return false
    }

    if isSameTree(root, subRoot) {
        return true
    }

    return isSubtree(root.Left, subRoot) ||
        isSubtree(root.Right, subRoot)
}

The Go implementation follows the same recursive structure as the Python solution.

The main difference is handling nil pointers explicitly instead of Python's None. Go also requires defining the recursive helper function using a variable declaration before assignment so the closure can reference itself recursively.

No integer overflow concerns exist because node values remain within small constraint bounds.

Worked Examples

Example 1

root = [3,4,5,1,2]
subRoot = [4,1,2]

Tree structure:

        3
       / \
      4   5
     / \
    1   2

Subtree:

      4
     / \
    1   2

DFS Traversal

Current Node Match Attempt Result
3 Compare with subRoot root 4 Fail
4 Compare with subRoot root 4 Continue
1 Compare child nodes Match
2 Compare child nodes Match
Entire subtree All nodes match True

Detailed comparison at node 4:

node1 node2 Result
4 4 Match
1 1 Match
2 2 Match
None None Match

Since every corresponding node matches structurally and by value, the answer is true.

Example 2

root = [3,4,5,1,2,null,null,null,null,0]
subRoot = [4,1,2]

Tree structure:

        3
       / \
      4   5
     / \
    1   2
       /
      0

Subtree:

      4
     / \
    1   2

DFS Traversal

Current Node Match Attempt Result
3 Compare with 4 Fail
4 Compare subtree Continue
1 Match Continue
2 Structure mismatch Fail

The important mismatch occurs here:

node1 node2 Result
2 2 Value match
0 None Structure mismatch

Although node values initially match, the subtree rooted at 2 contains an extra child 0, so the trees are not identical.

The final answer is false.

Complexity Analysis

Measure Complexity Explanation
Time O(N × M) Each node in root may compare against all nodes in subRoot
Space O(H) Recursive call stack depth depends on tree height

Here:

  • N is the number of nodes in root
  • M is the number of nodes in subRoot
  • H is the maximum tree height

In the worst case, every node in root triggers a full subtree comparison. Each comparison may visit all nodes in subRoot, producing O(N × M) time complexity.

The recursive space complexity depends on tree height because recursive DFS calls are stored on the call stack. In a skewed tree, height may reach O(N).

Test Cases

# Definition for testing
class TreeNode:
    def __init__(self, val=0, left=None, right=None):
        self.val = val
        self.left = left
        self.right = right

def build_tree(values):
    if not values:
        return None

    nodes = [
        TreeNode(v) if v is not None else None
        for v in values
    ]

    kids = nodes[::-1]
    root = kids.pop()

    for node in nodes:
        if node:
            if kids:
                node.left = kids.pop()
            if kids:
                node.right = kids.pop()

    return root

solution = Solution()

# Example 1
root = build_tree([3, 4, 5, 1, 2])
subRoot = build_tree([4, 1, 2])
assert solution.isSubtree(root, subRoot) is True  # basic matching subtree

# Example 2
root = build_tree([3, 4, 5, 1, 2, None, None, None, None, 0])
subRoot = build_tree([4, 1, 2])
assert solution.isSubtree(root, subRoot) is False  # extra node breaks match

# Single node equal
root = build_tree([1])
subRoot = build_tree([1])
assert solution.isSubtree(root, subRoot) is True  # identical single node trees

# Single node different
root = build_tree([1])
subRoot = build_tree([2])
assert solution.isSubtree(root, subRoot) is False  # different values

# Deep subtree match
root = build_tree([1, 2, 3, 4, 5, 6, 7])
subRoot = build_tree([3, 6, 7])
assert solution.isSubtree(root, subRoot) is True  # subtree deep in tree

# Duplicate values but different structure
root = build_tree([1, 1, 1])
subRoot = build_tree([1, None, 1])
assert solution.isSubtree(root, subRoot) is False  # structure mismatch

# Entire tree is subtree of itself
root = build_tree([1, 2, 3])
subRoot = build_tree([1, 2, 3])
assert solution.isSubtree(root, subRoot) is True  # identical trees

# Left skewed tree
root = build_tree([1, 2, None, 3, None, 4])
subRoot = build_tree([2, 3, None])
assert solution.isSubtree(root, subRoot) is True  # skewed structure

# No matching subtree
root = build_tree([1, 2, 3])
subRoot = build_tree([4])
assert solution.isSubtree(root, subRoot) is False  # value never appears

Test Summary

Test Why
Example 1 Validates standard successful subtree match
Example 2 Validates structural mismatch detection
Single node equal Smallest valid matching trees
Single node different Smallest non matching trees
Deep subtree match Ensures DFS searches entire tree
Duplicate values Ensures structure matters, not only values
Entire tree match Confirms a tree is its own subtree
Left skewed tree Tests unbalanced recursion paths
No matching subtree Ensures false result when absent

Edge Cases

Duplicate Values in Multiple Locations

A common mistake is assuming that matching node values imply subtree equality. Consider a tree containing many nodes with the same value. The algorithm must still verify full structural equality. The helper function isSameTree recursively compares both structure and values, preventing false positives.

Extra Descendants in the Main Tree

A subtree candidate may initially appear to match but contain extra descendants deeper in the tree. This is exactly what happens in Example 2. The algorithm correctly detects this because a None child in subRoot does not match a real node in root.

Highly Unbalanced Trees

Skewed trees can create deep recursive chains. A naive iterative implementation might mishandle traversal order or subtree boundaries. The recursive DFS naturally handles left skewed and right skewed trees correctly because each recursive call independently validates subtree structure.

Entire Tree Equality

The problem states that a tree is considered a subtree of itself. Some implementations mistakenly search only child nodes and forget to compare the current root directly. This solution first checks isSameTree(root, subRoot) before recursing into children, ensuring identical full trees return true.