Skip to main content

🟩 Subtree of Another Tree (#572)

🔗 Problem Link​

📋 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

Example 2​

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

🔑 Key Insights & Approach​

Core Observation: Check if current node matches subRoot using isSameTree. If not, recursively check left and right subtrees.

Why DFS with Tree Comparison?

  • O(m * n) time where m = root nodes, n = subRoot nodes
  • O(h) space for recursion
  • Reuses tree comparison logic

Approaches:

  1. DFS with isSameTree helper: O(m * n) time
  2. Serialize trees and check substring: O(m + n) time but complex

Pattern: "Tree Pattern Matching" using recursive comparison.

🐍 Solution: Python​

Approach: DFS with Helper Function​

Time Complexity: O(m * n) | Space Complexity: O(h)

from typing import Optional

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

class Solution:
    def isSubtree(self, root: Optional[TreeNode], subRoot: Optional[TreeNode]) -> bool:
        if not subRoot:
            return True
        if not root:
            return False

        # Check if trees match at current node
        if self.isSameTree(root, subRoot):
            return True

        # Check left and right subtrees
        return self.isSubtree(root.left, subRoot) or self.isSubtree(root.right, subRoot)

    def isSameTree(self, p: Optional[TreeNode], q: Optional[TreeNode]) -> bool:
        if not p and not q:
            return True
        if not p or not q:
            return False
        if p.val != q.val:
            return False

        return self.isSameTree(p.left, q.left) and self.isSameTree(p.right, q.right)

🔵 Solution: Golang​

Approach: DFS with Helper​

Time Complexity: O(m * n) | Space Complexity: O(h)

type TreeNode struct {
    Val   int
    Left  *TreeNode
    Right *TreeNode
}

func isSubtree(root *TreeNode, subRoot *TreeNode) bool {
    if subRoot == nil {
        return true
    }
    if root == nil {
        return false
    }

    if isSameTree(root, subRoot) {
        return true
    }

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

func isSameTree(p *TreeNode, q *TreeNode) bool {
    if p == nil && q == nil {
        return true
    }
    if p == nil || q == nil {
        return false
    }
    if p.Val != q.Val {
        return false
    }

    return isSameTree(p.Left, q.Left) && isSameTree(p.Right, q.Right)
}

📚 References​