Symmetric Tree, Same Tree, and Subtree Problems

Tree structure comparison problems form a closely related family. Once you understand how to compare two trees node-by-node, variations like symmetry, subtree checks, and flip equivalence become straightforward extensions. These problems appear frequently in interviews because they test recursive thinking and edge case handling.

TreeNode definition

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

Same tree

LeetCode 100: Given the roots of two binary trees, check if they are structurally identical with the same node values.

This is the foundation for all comparison problems.

def isSameTree(p, q):
    """
    Check if two trees are identical.
    Time: O(min(n, m))  Space: O(min(h1, h2))
    """
    # Both null — same
    if not p and not q:
        return True

    # One null, other not — different
    if not p or not q:
        return False

    # Values differ
    if p.val != q.val:
        return False

    # Both subtrees must match
    return (isSameTree(p.left, q.left) and
            isSameTree(p.right, q.right))

Iterative version

from collections import deque

def isSameTree_iterative(p, q):
    """Iterative BFS comparison."""
    queue = deque([(p, q)])

    while queue:
        n1, n2 = queue.popleft()

        if not n1 and not n2:
            continue
        if not n1 or not n2:
            return False
        if n1.val != n2.val:
            return False

        queue.append((n1.left, n2.left))
        queue.append((n1.right, n2.right))

    return True

Time complexity

O(min(n, m)) where n and m are the sizes of the two trees. We stop as soon as we find a mismatch, so in the best case we return early. In the worst case (identical trees), we visit every node in the smaller tree.

Symmetric tree

LeetCode 101: Check if a binary tree is a mirror of itself (symmetric around the center).

A tree is symmetric if the left subtree is a mirror reflection of the right subtree. This means:

• left.val == right.val
• left.left mirrors right.right (outer pair)
• left.right mirrors right.left (inner pair)

def isSymmetric(root):
    """
    Check if a tree is symmetric (mirror of itself).
    Time: O(n)  Space: O(h)
    """
    if not root:
        return True

    def isMirror(left, right):
        if not left and not right:
            return True
        if not left or not right:
            return False
        if left.val != right.val:
            return False

        # Outer pair and inner pair must both mirror
        return (isMirror(left.left, right.right) and
                isMirror(left.right, right.left))

    return isMirror(root.left, root.right)

The key difference from isSameTree

In isSameTree, we compare left.left with right.left (same position). In isMirror, we compare left.left with right.right (mirror positions). This single change turns equality into symmetry.

Same Tree:                    Symmetric (Mirror):
left.left  == right.left      left.left  == right.right
left.right == right.right     left.right == right.left

Iterative version with queue

def isSymmetric_iterative(root):
    """Iterative BFS mirror check."""
    if not root:
        return True

    queue = deque([(root.left, root.right)])

    while queue:
        left, right = queue.popleft()

        if not left and not right:
            continue
        if not left or not right:
            return False
        if left.val != right.val:
            return False

        # Enqueue mirror pairs
        queue.append((left.left, right.right))   # Outer
        queue.append((left.right, right.left))   # Inner

    return True

Walkthrough

         1
        / \
       2   2
      / \ / \
     3  4 4  3

isMirror(2, 2): vals match
  isMirror(3, 3): vals match, both leaves → True
  isMirror(4, 4): vals match, both leaves → True
→ True

Not symmetric:

         1
        / \
       2   2
        \   \
         3   3

isMirror(2, 2): vals match
  isMirror(None, 3): one null → False
→ False

Subtree of another tree

LeetCode 572: Given two trees root and subRoot, check if subRoot is a subtree of root. A subtree must include all descendants of the starting node.

Approach 1: recursive comparison O(n * m)

For each node in root, check if the subtree rooted there equals subRoot.

def isSubtree(root, subRoot):
    """
    Check if subRoot is a subtree of root.
    Time: O(n * m) worst case
    Space: O(h) recursion
    """
    if not root:
        return False

    # Check if tree rooted at current node matches subRoot
    if isSameTree(root, subRoot):
        return True

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

Why O(n * m)?

In the worst case, we call isSameTree at every node of root (n nodes), and each call takes O(m) where m is the size of subRoot. Consider a skewed tree where every node has the same value — isSameTree nearly matches at every position before failing at the last node.

Approach 2: serialization O(n + m)

Serialize both trees to strings and use string matching (KMP or similar) to check if one is a substring of the other.

def isSubtree_serialize(root, subRoot):
    """
    Serialization + string matching.
    Time: O(n + m)  Space: O(n + m)
    """
    def serialize(node):
        if not node:
            return "#"
        # Use delimiters to avoid false matches
        # e.g., node 12 should not match "1" + "2"
        return f",{node.val},{serialize(node.left)},{serialize(node.right)}"

    root_str = serialize(root)
    sub_str = serialize(subRoot)

    return sub_str in root_str

Why we need delimiters

Without proper delimiters, node value 12 could falsely match nodes 1 and 2. The comma separators and null markers (#) prevent this.

# Without delimiters: "12#" contains "2#" → false match!
# With delimiters: ",12,#,#" does not contain ",2,#,#" → correct

Approach 3: hash-based O(n + m)

Compute a hash for each subtree using Merkle-tree hashing. Two subtrees with the same hash are identical (with high probability).

def isSubtree_hash(root, subRoot):
    """
    Merkle tree hashing approach.
    Time: O(n + m)  Space: O(n + m)
    """
    def compute_hash(node):
        if not node:
            return hash(None)
        left_hash = compute_hash(node.left)
        right_hash = compute_hash(node.right)
        return hash((node.val, left_hash, right_hash))

    target_hash = compute_hash(subRoot)
    found = False

    def check(node):
        nonlocal found
        if not node:
            return hash(None)
        left_hash = check(node.left)
        right_hash = check(node.right)
        current_hash = hash((node.val, left_hash, right_hash))

        if current_hash == target_hash:
            # Verify with isSameTree to avoid hash collision
            if isSameTree(node, subRoot):
                found = True

        return current_hash

    check(root)
    return found

Flip equivalent binary trees

LeetCode 951: Two binary trees are flip equivalent if you can make one equal to the other by flipping (swapping left and right children) at some nodes.

def flipEquiv(root1, root2):
    """
    Check if two trees are flip equivalent.
    Time: O(min(n1, n2))  Space: O(min(h1, h2))
    """
    # Both null
    if not root1 and not root2:
        return True

    # One null
    if not root1 or not root2:
        return False

    # Values differ
    if root1.val != root2.val:
        return False

    # Either the children match directly, or they match when flipped
    no_flip = (flipEquiv(root1.left, root2.left) and
               flipEquiv(root1.right, root2.right))

    flip = (flipEquiv(root1.left, root2.right) and
            flipEquiv(root1.right, root2.left))

    return no_flip or flip

How flip equivalence relates to symmetry

Problem	Comparison	Left-Left	Left-Right
Same Tree	Exact match	left↔left	right↔right
Symmetric	Mirror	left↔right	right↔left
Flip Equiv	Either	(left↔left AND right↔right) OR (left↔right AND right↔left)

Flip equivalence is the most general — it allows both the “same” and “mirror” configurations at each node independently.

Time complexity

The worst case for flip equivalence is O(n) where n is the size of the smaller tree. At each node, we try two options, but since the tree structure constrains the comparison, we do not get exponential blowup. Each node is visited at most a constant number of times.

Actually, let me clarify: in the worst case, the no_flip or flip short-circuits. If no_flip is True, we skip flip. If no_flip is False, we evaluate flip. In degenerate cases, we might evaluate both, but each subtree pair is compared at most twice, giving O(n) overall.

Invert binary tree

LeetCode 226: While not a comparison problem, inverting a tree is closely related. Inverting then comparing equals symmetry checking.

def invertTree(root):
    """
    Invert (mirror) a binary tree.
    Time: O(n)  Space: O(h)
    """
    if not root:
        return None

    root.left, root.right = invertTree(root.right), invertTree(root.left)
    return root

Connection to symmetry: A tree is symmetric if and only if it equals its own inversion.

def isSymmetric_via_invert(root):
    """Alternative: invert a copy and compare."""
    import copy
    inverted = invertTree(copy.deepcopy(root))
    return isSameTree(root, inverted)

This is less efficient (two passes + deep copy) but shows the conceptual relationship.

Complexity summary

Problem	Time	Space	Key insight
Same Tree	O(n)	O(h)	Compare node-by-node
Symmetric	O(n)	O(h)	Mirror comparison (swap inner/outer)
Subtree (recursive)	O(n*m)	O(h)	isSameTree at every node
Subtree (serialize)	O(n+m)	O(n+m)	String matching
Flip Equivalent	O(n)	O(h)	Try both flip and no-flip
Invert Tree	O(n)	O(h)	Swap children recursively

Edge cases

def test_edge_cases():
    # Both empty
    assert isSameTree(None, None) == True
    assert isSymmetric(None) == True

    # One empty
    assert isSameTree(TreeNode(1), None) == False
    assert isSubtree(None, TreeNode(1)) == False

    # Single node
    root = TreeNode(1)
    assert isSymmetric(root) == True
    assert isSubtree(root, TreeNode(1)) == True
    assert isSubtree(root, TreeNode(2)) == False

    # Subtree is the entire tree
    assert isSubtree(root, root) == True

    # Duplicate values
    root = TreeNode(1, TreeNode(1), TreeNode(1))
    assert isSymmetric(root) == True

Practice problems

Problem	Difficulty	Link
Same Tree	Easy	LeetCode 100
Symmetric Tree	Easy	LeetCode 101
Subtree of Another Tree	Easy	LeetCode 572
Flip Equivalent Binary Trees	Medium	LeetCode 951
Invert Binary Tree	Easy	LeetCode 226
Univalued Binary Tree	Easy	LeetCode 965
Leaf-Similar Trees	Easy	LeetCode 872

Key takeaways

1. Same tree is the building block — symmetry and subtree both build on it
2. Symmetric tree = mirror comparison (left.left vs right.right)
3. Subtree check has O(n*m) recursive and O(n+m) serialization approaches
4. Flip equivalence tries both orientations at each node — it is the most general comparison
5. All these problems follow the same recursive template: handle null cases, compare values, recurse on children