Domain 1EasyCORE

Subtree of Another Tree

The problem asks us to determine whether a given binary tree `t` is a subtree of another binary tree `s`. A subtree of `s` is defined as a node in `s` and all its descendants. The structure and node values must match exactly.

Domain: Easy•Updated: 2026-08-31
#Algorithms#LeetCode#qwen2.5-coder:14b#Tree

572. Subtree of Another Tree

Model: qwen2.5-coder:14b
Topics: Tree
FAANG asked: 1
Acceptance rate: 44.6%


Problem Breakdown

The problem asks us to determine whether a given binary tree t is a subtree of another binary tree s. A subtree of s is defined as a node in s and all its descendants. The structure and node values must match exactly.

Inputs:

  • Two non-empty binary trees, s (the main tree) and t (the potential subtree).

Outputs:

  • A boolean value indicating whether t is a subtree of s.

Implicit Constraints or Tricky Edge Cases:

  • The trees can be large.
  • The values in the nodes could be negative or zero.
  • The trees might have duplicate values.

Intuition

A brute-force approach would involve checking every node in s to see if it matches the structure and values of t. This would result in a time complexity of O(n * m), where n is the number of nodes in s and m is the number of nodes in t.

The key insight is that we can use a recursive approach to check if any subtree of s is identical to t. We can leverage the properties of binary trees and perform a tree traversal to compare each node.

Approach

  1. Recursive Function: Define a helper function is_identical that checks if two trees are identical (i.e., have the same structure and values).
  2. Base Case for is_identical:
    • If both nodes are null, return true.
    • If one node is null and the other is not, return false.
    • If the values of the current nodes are different, return false.
  3. Recursive Case for is_identical:
    • Recursively check if the left subtrees are identical.
    • Recursively check if the right subtrees are identical.
  4. Main Function: Define a function is_subtree that checks if t is a subtree of s.
  5. Base Case for is_subtree:
    • If s is null, return false (since an empty tree cannot contain another non-empty tree).
  6. Recursive Case for is_subtree:
    • Check if the current nodes of s and t are identical using is_identical.
    • Recursively check if t is a subtree of the left or right subtree of s.

Complexity Analysis

  • Time Complexity: O(n * m) in the worst case, where n is the number of nodes in s and m is the number of nodes in t. This is because for each node in s, we might need to check if it matches t.
  • Space Complexity: O(h_s + h_t), where h_s is the height of s and h_t is the height of t. This is due to the recursion stack.

Solution

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

def is_identical(s: TreeNode, t: TreeNode) -> bool:
    if not s and not t:
        return True
    if not s or not t:
        return False
    if s.val != t.val:
        return False
    return (is_identical(s.left, t.left) and 
            is_identical(s.right, t.right))

def is_subtree(s: TreeNode, t: TreeNode) -> bool:
    if not s:
        return False
    if is_identical(s, t):
        return True
    return (is_subtree(s.left, t) or 
            is_subtree(s.right, t))

Edge Cases Handled

  • Empty t: The function will correctly identify that an empty tree is a subtree of any tree.
  • Large Trees: The recursive approach handles large trees by breaking them down into smaller subproblems.
  • Duplicate Values: The function correctly compares the structure and values, so duplicate values do not affect the result.