Same Tree: Multiple Solutions and Complexity Analysis

Introduction to the Same Tree Problem

The "Same Tree" problem is a classic algorithmic challenge frequently encountered in coding interviews and computer science curricula. Given the roots of two binary trees, the task is to determine whether the two trees are structurally identical and have the same node values at every corresponding position. While the problem statement is deceptively simple, it offers an excellent opportunity to explore multiple algorithmic approaches, including recursion, iteration with stacks, and level-order traversal using queues.

Understanding this problem deeply matters because it forms the foundation for more complex tree comparison tasks, subtree detection, and serialization-based equality checks. It also reinforces essential concepts such as tree traversal strategies, recursion patterns, and complexity analysis — skills that transfer directly to real-world scenarios like comparing hierarchical data structures, validating document trees, and detecting changes in file systems.

Problem Definition

Two binary trees are considered the same if they are structurally identical and all corresponding nodes have the same value. Formally, trees p and q are the same when:

• Both p and q are null (empty trees are equal).
• Both p and q are non-null, their root values are equal, and their left subtrees are the same, and their right subtrees are the same.
• Otherwise, they are not the same.

Here is the typical tree node definition used across all solutions:

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

Solution 1: Recursive Depth-First Approach

The most intuitive solution leverages recursion. Since the definition of "same tree" is itself recursive, we can translate it almost directly into code. At each step, we compare the current nodes of both trees. If both are null, they match. If only one is null, they differ. If both exist, we compare their values and recursively check both the left and right subtrees.

Implementation

def isSameTree(p: TreeNode, q: TreeNode) -> bool:
    # Both nodes are null - structurally identical at this branch
    if not p and not q:
        return True
    # Only one node is null - structure differs
    if not p or not q:
        return False
    # Both nodes exist - compare values and recurse on children
    if p.val != q.val:
        return False
    return isSameTree(p.left, q.left) and isSameTree(p.right, q.right)

Complexity Analysis

Time Complexity: O(min(n, m)), where n and m are the number of nodes in trees p and q. In the worst case, we visit every node of the smaller tree before discovering a mismatch or confirming equality. When the trees are identical, we visit all nodes of both trees, yielding O(n).

Space Complexity: O(min(h1, h2)), where h1 and h2 are the heights of the trees. This accounts for the recursion stack. In the worst case of a skewed tree, the height equals the number of nodes, giving O(n). For a balanced tree, the height is O(log n).

Solution 2: Iterative Approach Using Two Stacks

Recursion is elegant, but some environments limit stack depth, and some teams prefer explicit control over traversal. We can convert the recursive approach into an iterative one using two explicit stacks. We push corresponding nodes from both trees onto their respective stacks and compare them as we pop.

Implementation

def isSameTree(p: TreeNode, q: TreeNode) -> bool:
    stack_p = [p]
    stack_q = [q]

    while stack_p and stack_q:
        node_p = stack_p.pop()
        node_q = stack_q.pop()

        # Both null - continue to next pair
        if not node_p and not node_q:
            continue
        # One null, the other not - mismatch
        if not node_p or not node_q:
            return False
        # Values differ
        if node_p.val != node_q.val:
            return False

        # Push children in consistent order (right then left)
        stack_p.append(node_p.right)
        stack_p.append(node_p.left)
        stack_q.append(node_q.right)
        stack_q.append(node_q.left)

    # Both stacks must be empty for trees to be identical
    return not stack_p and not stack_q

Complexity Analysis

Time Complexity: O(n), identical to the recursive version. Each node is processed exactly once.

Space Complexity: O(h), where h is the height of the tree. The stacks hold at most one path from root to leaf at any time. For skewed trees this becomes O(n); for balanced trees it is O(log n).

Solution 3: Level-Order Traversal Using Queues

A breadth-first approach compares trees level by level. Using two queues, we dequeue corresponding nodes, compare them, and enqueue their children. This approach can detect structural mismatches earlier in wide trees because it processes nodes top-down across each level rather than diving deep into one branch first.

Implementation

from collections import deque

def isSameTree(p: TreeNode, q: TreeNode) -> bool:
    queue_p = deque([p])
    queue_q = deque([q])

    while queue_p and queue_q:
        node_p = queue_p.popleft()
        node_q = queue_q.popleft()

        if not node_p and not node_q:
            continue
        if not node_p or not node_q:
            return False
        if node_p.val != node_q.val:
            return False

        queue_p.append(node_p.left)
        queue_p.append(node_p.right)
        queue_q.append(node_q.left)
        queue_q.append(node_q.right)

    return not queue_p and not queue_q

Complexity Analysis

Time Complexity: O(n). Every node is enqueued and dequeued at most once.

Space Complexity: O(w), where w is the maximum width of the tree. In the worst case, the bottom level of a complete binary tree contains roughly n/2 nodes, so the space complexity is O(n). This is generally worse than the stack-based approach for balanced trees, where the stack approach uses O(log n) space.

Solution 4: Serialization-Based Comparison

An alternative strategy serializes both trees into strings or lists and then compares the serialized forms. This approach is useful when you need to cache or hash tree structures, or when you want to compare many trees against a reference efficiently by precomputing the serialization once.

Implementation

def serialize(root: TreeNode) -> str:
    if not root:
        return "N"
    return f"{root.val},{serialize(root.left)},{serialize(root.right)}"

def isSameTree(p: TreeNode, q: TreeNode) -> bool:
    return serialize(p) == serialize(q)

Complexity Analysis

Time Complexity: O(n + m). Both trees are fully serialized before comparison. Unlike the early-exit approaches, this method always traverses both trees completely, even if the first nodes differ.

Space Complexity: O(n + m) for the serialized strings, plus O(h) for the recursion stack during serialization. This is the least efficient approach for a single comparison but becomes advantageous when comparing one tree against many pre-serialized candidates.

Comparing the Approaches

• Recursive DFS: Cleanest code, best for interviews, but risks stack overflow on very deep trees.
• Iterative DFS with stacks: Avoids recursion limits, same asymptotic complexity, slightly more verbose.
• Iterative BFS with queues: Compares level by level, useful when mismatches are expected near the top, but uses more memory on wide trees.
• Serialization: Inefficient for single comparisons but powerful for caching, hashing, and bulk comparisons.

Best Practices

When implementing tree comparison in production code, consider the following guidelines. First, always handle the null cases explicitly before accessing node properties to avoid null reference errors. Second, prefer early exit — return False as soon as a mismatch is found rather than traversing the entire tree. Third, be mindful of recursion depth; if your trees can be very deep or unbalanced, use the iterative stack-based approach to avoid stack overflow. Fourth, if you need to compare the same tree against many others repeatedly, precompute its serialization and compare strings, which turns repeated O(n) traversals into O(n) string comparisons. Finally, write unit tests covering edge cases such as both trees empty, one tree empty, trees with identical structure but different values, trees with different structure but identical values, and large skewed trees to validate both correctness and performance.

Conclusion

The Same Tree problem is a deceptively simple challenge that opens the door to a rich discussion of tree traversal strategies, recursion versus iteration, and time-space tradeoffs. The recursive DFS solution remains the most elegant and is usually the best starting point, while the iterative variants provide robustness against deep recursion and offer different memory characteristics. The serialization approach, though less efficient for one-off comparisons, demonstrates how reframing a problem can unlock optimizations in broader use cases. By understanding all four solutions and their complexity profiles, you will be well-equipped not only to solve this specific problem but also to tackle related challenges such as subtree checking, tree mirroring, and symmetric tree validation with confidence.