Same Tree

A tree comparison fails the moment you forget that a missing child is also part of the structure.

The clean Same Tree solution is synchronized depth-first search (DFS): compare one node from p with the corresponding node from q, then compare their left children together and their right children together. Every paired position must satisfy the same local contract:

1. Both nodes are absent.
2. Exactly one node is absent.
3. Both nodes exist and have equal values.

Only the first and third cases can continue toward a True result.

Read the contract as paired positions

The function receives two binary-tree roots, p and q, and returns a boolean.

The trees are the same only when:

• Their structures match.
• Every corresponding node has the same value.
• An empty tree matches another empty tree.
• A missing child in one tree matches a missing child in the same position in the other tree.

That last condition is where many plausible solutions break.

Consider these two trees:

p:       1          q:       1
         /                   \
        2                     2

Both trees contain 1 and 2, but the nodes occupy different positions. In p, 2 is the left child; in q, it is the right child. The trees are different.

A useful mental model is to put a transparent copy of one tree over the other. At every position, compare the two nodes underneath your finger:

• Two empty positions mean the shapes agree there.
• One empty position means the shapes diverge.
• Two present nodes require equal values.

That gives us the direction immediately:

Compare corresponding node pairs recursively. Stop at the first null mismatch or value mismatch.

Why value-only comparisons fail

A tempting approach is to collect the values from both trees and compare the resulting lists. That works only if the representation preserves missing children explicitly.

Without null markers, these shapes can collapse into the same value sequence:

[1, 2]

    1          1
   /            \
  2              2

A preorder-style traversal containing only values might produce [1, 2] for both. The list has discarded the information that distinguishes left from right.

You could build a full encoding that includes None for every missing child, then compare the two encodings. That is a valid approach because it preserves structure.

Paired DFS reaches the same information more directly. Instead of constructing two complete representations first, it examines both trees at the same time and keeps the correspondence visible. The useful state is already present in the problem: a pair of positions.

Derive the paired DFS recurrence

Define a helper:

same_tree(node_p, node_q)

It answers one precise question:

Are the subtrees rooted at node_p and node_q structurally identical, with equal values at every corresponding position?

Now derive its cases.

Case 1: both nodes are absent

node_p is None and node_q is None

Both subtrees ended at the same position. There is no remaining structure or value to compare, so this pair matches.

Return True.

Case 2: exactly one node is absent

node_p is None or node_q is None

One tree has a node at this position and the other does not. Their structures differ.

Return False.

This check must happen before reading either node's value. Accessing node_p.val when node_p is None would fail, and the null mismatch is already decisive.

Case 3: both nodes exist but values differ

node_p.val != node_q.val

The structures may still look identical below this point, but corresponding nodes already disagree.

Return False.

Case 4: values match

Now both current nodes exist and have equal values. Their subtrees must also match:

same_tree(node_p.left, node_q.left) and \
same_tree(node_p.right, node_q.right)

The left child must stay paired with the left child. The right child must stay paired with the right child. Swapping those pairings would test a different structural relationship.

The recurrence is therefore:

[ S(p, q) = \begin{cases} \text{True} & \text{if } p = \text{None} \text{ and } q = \text{None} \ \text{False} & \text{if exactly one of } p, q \text{ is None} \ \text{False} & \text{if } p.val \ne q.val \ S(p.left, q.left) \land S(p.right, q.right) & \text{otherwise} \end{cases} ]

The AND is essential. Matching the left subtrees cannot compensate for a mismatch on the right.

Invariant: same_tree(p, q) returns True exactly when the two subtrees rooted at p and q match in both structure and corresponding values.

Why the recurrence is complete

The helper checks the current pair first, then delegates each child position to a smaller pair of subtrees.

The base cases are locally correct:

• Two absent nodes represent matching empty subtrees.
• One absent node represents a structural mismatch.
• Two present nodes with different values represent a value mismatch.

For two present nodes with equal values, every descendant position belongs to exactly one of two branches: the left subtree or the right subtree. The recursive calls inspect both branches. The and operation returns True only when both calls return True.

That covers the entire pair of trees. A finite tree eventually reaches a leaf's missing children, so the recursive process reaches a base case on every path. No node or missing-child position is skipped.

This is the difference between code that passes a few examples and code whose correctness follows from the problem definition: every structural and value obligation has a matching branch in the recurrence.

Dry-run: asymmetric null children

Use the structurally different pair:

p = [1, 2]
q = [1, None, 2]

Their shape is:

p:       1          q:       1
        /                    \
       2                      2

The synchronized calls look like this:

same_tree(1, 1)
├── same_tree(2, None)  -> False
└── not evaluated

The roots both exist and both contain 1, so the comparison continues to their children. The left pair is (2, None): one node exists and the other does not. That is an immediate structural mismatch.

Python's short-circuit and means the right comparison is not needed. The right-side 2 cannot repair the failed left-side comparison. Correspondence is positional, not based on whether the same value appears somewhere else.

Two other important traces are short:

same_tree(None, None) -> True

For a matching nonempty pair:

same_tree(1, 1)
├── same_tree(2, 2)
│   ├── same_tree(None, None) -> True
│   └── same_tree(None, None) -> True
└── same_tree(3, 3)
    ├── same_tree(None, None) -> True
    └── same_tree(None, None) -> True

Every corresponding position passes, so the root call returns True.

Recursive DFS implementation in Python

Here is the primary implementation:

from typing import Optional


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


def is_same_tree(
    p: Optional[TreeNode],
    q: Optional[TreeNode],
) -> bool:
    # Both positions are empty: the subtrees match here.
    if p is None and q is None:
        return True

    # Exactly one position is empty: the structures differ.
    if p is None or q is None:
        return False

    # Both nodes exist, so compare their values.
    if p.val != q.val:
        return False

    # Matching nodes require matching left and right subtrees.
    return (
        is_same_tree(p.left, q.left)
        and is_same_tree(p.right, q.right)
    )

The order of the checks is deliberate:

1. Handle the pair where both nodes are absent.
2. Reject a one-sided absence.
3. Reject unequal values.
4. Recurse into corresponding children.

Once the code reaches the final return, both nodes are known to exist and have equal values. That makes accessing .left, .right, and .val safe.

The recursive call on the right may never run if the left call returns False. This is short-circuit evaluation. It does not weaken the correctness condition: logically, both subtrees must match; operationally, we stop when one failed subtree has already settled the answer.

I would start with this version in an interview because the code mirrors the recurrence almost line for line. The control flow is visible, and every branch has a job you can explain.

Iterative DFS: store paired nodes

Recursion uses the language call stack to remember which pair of nodes is being processed. An iterative version stores that state explicitly in a stack.

The stack must contain pairs (p_node, q_node). Traversing the two trees independently is wrong because the problem is about correspondence, not two unrelated visits.

def is_same_tree_iterative(
    p: Optional[TreeNode],
    q: Optional[TreeNode],
) -> bool:
    stack = [(p, q)]

    while stack:
        node_p, node_q = stack.pop()

        # Both positions are empty.
        if node_p is None and node_q is None:
            continue

        # Exactly one position is empty.
        if node_p is None or node_q is None:
            return False

        # Corresponding values differ.
        if node_p.val != node_q.val:
            return False

        # Preserve correspondence for both child positions.
        stack.append((node_p.left, node_q.left))
        stack.append((node_p.right, node_q.right))

    return True

The iterative and recursive versions perform the same logical checks. Only the memory holding unfinished work changes:

• Recursive DFS: the call stack stores the current path of paired nodes.
• Iterative DFS: an explicit stack stores pending paired child comparisons.
• Readability: recursion mirrors the mathematical definition more closely.
• Depth considerations: iteration avoids relying on the language's recursion limit and makes pending state explicit.

Neither implementation is universally superior. For this problem, recursive DFS is usually the clearest first answer. If the input can contain a very deep skewed tree, or the language's call stack is a practical constraint, the iterative version gives you direct control over that state.

Complexity and edge-case checklist

Let n and m be the numbers of nodes in the two trees.

Time complexity

The algorithm performs constant work for each paired position it reaches. In the worst case, it examines all nodes in both trees:

[ O(n + m) ]

It may finish earlier when it finds a null mismatch or unequal value.

Space complexity

For recursive DFS, let h be the maximum depth reached before the function returns. The active call chain uses:

[ O(h) ]

additional space.

The iterative DFS also uses O(h) auxiliary space for the maximum number of paired positions pending during the depth-first traversal. It moves that state from the language call stack into an explicit data structure.

Before submitting, test these cases mentally:

• Both roots are None.
• Exactly one root is None.
• The root values differ.
• Values match but a child exists on only one side.
• A node appears on the left in one tree and the right in the other.
• The trees contain repeated values but have different shapes.
• The trees are identical and include several missing children.
• A deep, one-sided tree exercises recursion depth.

Reject shortcuts based only on node counts, value sets, or traversal values without null structure. Those checks answer weaker questions. Same Tree requires the exact shape and the exact value at every corresponding position.

The transferable pattern

When a problem compares two recursive structures position by position, carry the pair as the state.

Build the solution in this order:

1. Define the both-absent base case.
2. Reject one-sided absence.
3. Compare the current values.
4. Recurse on matching child positions.
5. Require every corresponding recursive result to pass.

That is the reusable move. The tree is only the setting. The deeper pattern is synchronized recursion: two structures enter the same state together, and one local mismatch is enough to stop the comparison.