Subtree Problems: Substructures and Symmetry

Core Concept: Subtree problems center around the "simultaneous comparison of two trees." mastering the dual-pointer recursive approach provides a robust template for all variants.

Symmetric Tree (LeetCode 101)

Check if a tree is a mirror image of itself.

public boolean isSymmetric(TreeNode root) {
    if (root == null) return true;
    return checkSymmetry(root.left, root.right);
}

private boolean checkSymmetry(TreeNode left, TreeNode right) {
    if (left == null && right == null) return true;
    if (left == null || right == null) return false;
    
    return left.val == right.val
        && checkSymmetry(left.left,  right.right) // Outer pair matching
        && checkSymmetry(left.right, right.left);  // Inner pair matching
}

Same Tree (LeetCode 100)

Precisely determine if two trees have identical structures and node values.

public boolean isSameTree(TreeNode p, TreeNode q) {
    if (p == null && q == null) return true;
    if (p == null || q == null) return false;
    
    return p.val == q.val
        && isSameTree(p.left, q.left)   // Same-side comparison
        && isSameTree(p.right, q.right); 
}

Comparison: "Same Tree" compares corresponding sides (l.left vs r.left), while "Symmetric Tree" compares mirror opposites (l.left vs r.right).

Subtree of Another Tree (LeetCode 572)

Check if subRoot is structurally identical to any subtree within root.

public boolean isSubtree(TreeNode root, TreeNode subRoot) {
    if (root == null) return false;
    // Check if the current tree matches target, or if the target is in children
    return isSameTree(root, subRoot)
        || isSubtree(root.left, subRoot)
        || isSubtree(root.right, subRoot);
}

private boolean isSameTree(TreeNode p, TreeNode q) {
    if (p == null && q == null) return true;
    if (p == null || q == null) return false;
    return p.val == q.val 
        && isSameTree(p.left, q.left) 
        && isSameTree(p.right, q.right);
}

Complexity: O(M * N) in worst case. Can be optimized to O(M + N) using serialization and KMP string-search algorithms.

Flip Equivalent Binary Trees (LeetCode 951)

Check if two trees can become identical by flipping arbitrary nodes' subtrees.

public boolean flipEquiv(TreeNode root1, TreeNode root2) {
    if (root1 == null && root2 == null) return true;
    if (root1 == null || root2 == null) return false;
    if (root1.val != root2.val) return false;
    
    // Case 1: No flip needed for this node's children
    boolean noFlip = flipEquiv(root1.left, root2.left) && flipEquiv(root1.right, root2.right);
    // Case 2: Matching after a flip
    boolean flip   = flipEquiv(root1.left, root2.right) && flipEquiv(root1.right, root2.left);
    
    return noFlip || flip;
}

Mirror of a Binary Tree (LeetCode 226 / Invert Tree)

Standard recursive inversion (already covered, here is an iterative alternative using a stack):

public TreeNode mirrorTree(TreeNode root) {
    if (root == null) return null;
    Deque<TreeNode> stack = new ArrayDeque<>();
    stack.push(root);
    
    while (!stack.isEmpty()) {
        TreeNode node = stack.pop();
        // Swap immediate children
        TreeNode temp = node.left;
        node.left = node.right;
        node.right = temp;
        
        // Push children back to stack for further processing
        if (node.left != null) stack.push(node.left);
        if (node.right != null) stack.push(node.right);
    }
    return root;
}

Summary Table