# LeetCode 572: Subtree of Another Tree ## Problem Restatement We are given the roots of two binary trees: | Name | Meaning | |---|---| | `root` | The larger tree | | `subRoot` | The tree we want to find inside `root` | Return `True` if there is a subtree of `root` that has exactly the same structure and node values as `subRoot`. A subtree means a node and all of its descendants. A tree is also considered a subtree of itself. The official constraints say the number of nodes in `root` is in the range `[1, 2000]`, the number of nodes in `subRoot` is in the range `[1, 1000]`, and node values are between `-10^4` and `10^4`. ## Input and Output | Item | Meaning | |---|---| | Input | `root` and `subRoot`, two binary tree roots | | Output | Boolean | | Return `True` when | Some subtree of `root` is identical to `subRoot` | | Return `False` when | No matching subtree exists | Example function shape: ```python def isSubtree(root: Optional[TreeNode], subRoot: Optional[TreeNode]) -> bool: ... ``` ## Examples Example 1: ```python root = [3, 4, 5, 1, 2] subRoot = [4, 1, 2] ``` The tree rooted at value `4` inside `root` is: ```python 4 / \ 1 2 ``` This is exactly the same as `subRoot`. So the answer is: ```python True ``` Example 2: ```python root = [3, 4, 5, 1, 2, None, None, None, None, 0] subRoot = [4, 1, 2] ``` There is a node with value `4`, but its subtree is: ```python 4 / \ 1 2 / 0 ``` This is not the same as `subRoot`, because the node `2` has an extra child. So the answer is: ```python False ``` ## First Thought: Compare `subRoot` at Every Node A subtree of `root` must start at some node in `root`. So a direct approach is: 1. Visit every node in `root`. 2. At each node, check whether the subtree starting there is identical to `subRoot`. 3. Return `True` if any comparison matches. This naturally gives us two recursive functions: | Function | Purpose | |---|---| | `sameTree(a, b)` | Checks whether two trees are identical | | `isSubtree(root, subRoot)` | Searches for a matching starting node | ## Key Insight There are two different questions: First, are these two trees identical? Second, does this smaller tree appear anywhere inside the larger tree? The first question is solved by comparing two trees node by node. The second question is solved by DFS over `root`. At each node of `root`, we ask the first question. ## Identical Tree Check Two binary trees are identical if all three conditions hold: 1. Their roots are both missing, or both present. 2. Their root values are equal. 3. Their left subtrees and right subtrees are identical. In code: ```python sameTree(a.left, b.left) sameTree(a.right, b.right) ``` Both recursive checks must be true. ## Algorithm 1. Define `sameTree(a, b)`: 1. If both are `None`, return `True`. 2. If only one is `None`, return `False`. 3. If `a.val != b.val`, return `False`. 4. Return whether the left subtrees match and the right subtrees match. 2. Define `isSubtree(root, subRoot)`: 1. If `root` is `None`, return `False`. 2. If `sameTree(root, subRoot)` is true, return `True`. 3. Otherwise, search `root.left`. 4. Otherwise, search `root.right`. ## Correctness The helper `sameTree(a, b)` returns `True` exactly when the two trees have the same structure and the same values. It checks the current nodes first, then recursively checks the left and right children. If one side has a node where the other side has no node, it returns `False`, so structural differences are detected. The main function visits every possible root node of a subtree inside `root`. For each visited node, it calls `sameTree` to check whether the subtree rooted at that node is identical to `subRoot`. If the algorithm returns `True`, then it found a node in `root` whose full subtree matches `subRoot`, so `subRoot` is a subtree. If the algorithm returns `False`, then every possible subtree root in `root` was checked and none matched `subRoot`. Therefore, `subRoot` is not a subtree of `root`. ## Complexity Let: | Symbol | Meaning | |---|---| | `n` | Number of nodes in `root` | | `m` | Number of nodes in `subRoot` | | Metric | Value | Why | |---|---|---| | Time | `O(nm)` | In the worst case, we compare `subRoot` against many nodes in `root` | | Space | `O(h)` | Recursion stack depth from tree traversal | Here `h` is the height of the recursion stack. In a skewed tree, this can be `O(n + m)` during nested recursive calls. ## Implementation ```python from typing import Optional # Definition for a binary tree node. # class TreeNode: # def __init__(self, val: int = 0, left: Optional['TreeNode'] = None, right: Optional['TreeNode'] = None): # self.val = val # self.left = left # self.right = right class Solution: def isSubtree( self, root: Optional['TreeNode'], subRoot: Optional['TreeNode'], ) -> bool: def sameTree( a: Optional['TreeNode'], b: Optional['TreeNode'], ) -> bool: if a is None and b is None: return True if a is None or b is None: return False if a.val != b.val: return False return sameTree(a.left, b.left) and sameTree(a.right, b.right) if root is None: return False return ( sameTree(root, subRoot) or self.isSubtree(root.left, subRoot) or self.isSubtree(root.right, subRoot) ) ``` ## Code Explanation The helper handles empty trees first: ```python if a is None and b is None: return True if a is None or b is None: return False ``` Both missing means the structures match at this position. One missing means the structures differ. Then we compare values: ```python if a.val != b.val: return False ``` If the current nodes match, both child pairs must also match: ```python return sameTree(a.left, b.left) and sameTree(a.right, b.right) ``` The main search stops when the larger tree is exhausted: ```python if root is None: return False ``` Otherwise, it checks the current node as a possible subtree root, then searches the left and right subtrees. ## Serialization Version Another approach is to serialize both trees with null markers, then check whether the serialized `subRoot` appears inside the serialized `root`. The null markers are important. Without them, different tree shapes can produce ambiguous strings. ```python class Solution: def isSubtree( self, root: Optional['TreeNode'], subRoot: Optional['TreeNode'], ) -> bool: def serialize(node: Optional['TreeNode']) -> str: if node is None: return "#" return ( "^" + str(node.val) + "," + serialize(node.left) + "," + serialize(node.right) ) return serialize(subRoot) in serialize(root) ``` The recursive comparison version is usually clearer for this problem. ## Testing ```python class TreeNode: def __init__(self, val=0, left=None, right=None): self.val = val self.left = left self.right = right def run_tests(): s = Solution() root = TreeNode( 3, TreeNode(4, TreeNode(1), TreeNode(2)), TreeNode(5), ) subRoot = TreeNode(4, TreeNode(1), TreeNode(2)) assert s.isSubtree(root, subRoot) is True root = TreeNode( 3, TreeNode(4, TreeNode(1), TreeNode(2, TreeNode(0))), TreeNode(5), ) subRoot = TreeNode(4, TreeNode(1), TreeNode(2)) assert s.isSubtree(root, subRoot) is False root = TreeNode(1) subRoot = TreeNode(1) assert s.isSubtree(root, subRoot) is True root = TreeNode(1, TreeNode(1)) subRoot = TreeNode(1) assert s.isSubtree(root, subRoot) is True root = TreeNode(1, None, TreeNode(1)) subRoot = TreeNode(1, TreeNode(1)) assert s.isSubtree(root, subRoot) is False print("all tests passed") run_tests() ``` | Test | Why | |---|---| | Matching subtree | Basic positive case | | Extra child in `root` subtree | Same values near root, different structure | | Single-node equal trees | A tree can be a subtree of itself | | Single-node `subRoot` inside larger tree | Match may occur below the root | | Same values but wrong child side | Structure must match, not only values |