Same Tree

Problem

Given the roots of two binary trees p and q, decide whether the two trees are identical: they must have exactly the same shape, and every corresponding pair of nodes must hold the same value. Return True if they are identical, False otherwise.

Examples

Example 1

Input: p = [1,2,3], q = [1,2,3]
Output: True

Both trees are a root 1 with left child 2 and right child 3 — same structure, same values.

Example 2

Input: p = [1,2], q = [1,null,2]
Output: False

Both trees contain the values {1, 2}, but p’s 2 is a left child while q’s 2 is a right child — the shapes differ.

Example 3

Input: p = [1,2,1], q = [1,1,2]
Output: False

Same shape, but the children’s values are swapped: 2 vs 1 on the left, 1 vs 2 on the right.

Constraints

• The number of nodes in each tree is in the range [0, 100].
• -10^4 <= Node.val <= 10^4

The bounds are small, so any O(n) traversal is fine. The challenge is the structural comparison, not speed.

Think about it first

TL;DR

Parallel DFS on both trees — O(min(n, m)) time, O(h) space; an iterative pair-queue version works too.

Approach 1 — Brute force: serialize, then compare

Flatten each tree to a string with a traversal, then compare the strings. A plain preorder of values is wrong (Example 2’s trees both give “1,2”), so null children must be recorded explicitly to capture the shape.

# Definition for a binary tree node.
# class TreeNode:
#     def __init__(self, val=0, left=None, right=None):
#         self.val = val
#         self.left = left
#         self.right = right

from typing import Optional


def isSameTree(p: Optional[TreeNode], q: Optional[TreeNode]) -> bool:
    def serialize(node: Optional[TreeNode]) -> str:
        if not node:
            return "#"
        left = serialize(node.left)
        right = serialize(node.right)
        return f"({node.val},{left},{right})"

    return serialize(p) == serialize(q)

Complexity: O(n + m) time and O(n + m) space for the two strings. It walks both trees fully even when they differ at the root, and building strings only to compare them is indirect. Comparing the trees node by node is simpler and can stop at the first mismatch.

Approach 2 — Recursive parallel DFS

Two trees are identical iff their roots agree, their left subtrees are identical, and their right subtrees are identical. The problem’s definition is already a recursion. Walk both trees in lockstep (a depth-first search over pairs of nodes) and stop at the first disagreement.

# Definition for a binary tree node.
# class TreeNode:
#     def __init__(self, val=0, left=None, right=None):
#         self.val = val
#         self.left = left
#         self.right = right

from typing import Optional


def isSameTree(p: Optional[TreeNode], q: Optional[TreeNode]) -> bool:
    if p is None and q is None:
        return True
    if p is None or q is None:
        return False
    if p.val != q.val:
        return False
    return isSameTree(p.left, q.left) and isSameTree(p.right, q.right)

The two trees in Example 2 share the same values but differ in shape: in p the 2 is a left child, in q it is a right child.

graph TD
  subgraph tq["Tree q = [1,null,2]"]
    q1((1)) -- right --> q2((2))
  end
  subgraph tp["Tree p = [1,2]"]
    p1((1)) -- left --> p2((2))
  end

Walkthrough on Example 2 (p = [1,2], q = [1,null,2]):

1. Compare roots: both exist, 1 == 1 → recurse on children.
2. Left pair: p.left is node 2, q.left is None → exactly one is None → False.
3. The and short-circuits; the right pair is never examined. Answer: False.

Complexity: O(min(n, m)) time — the walk stops at the first mismatch and never visits more nodes than the smaller tree has. O(h) space for recursion (O(n) worst case for a skewed tree).

Approach 3 — Iterative with a queue of pairs

The recursion compares independent pairs of nodes, so any worklist of pairs (stack or queue) does the same job without recursion. With a FIFO queue this becomes breadth-first search: process node pairs level by level.

# Definition for a binary tree node.
# class TreeNode:
#     def __init__(self, val=0, left=None, right=None):
#         self.val = val
#         self.left = left
#         self.right = right

from collections import deque
from typing import Optional


def isSameTree(p: Optional[TreeNode], q: Optional[TreeNode]) -> bool:
    queue = deque([(p, q)])
    while queue:
        a, b = queue.popleft()
        if a is None and b is None:
            continue
        if a is None or b is None or a.val != b.val:
            return False
        queue.append((a.left, b.left))
        queue.append((a.right, b.right))
    return True

Walkthrough on Example 1 (p = q = [1,2,3]): pop (1,1) — equal, enqueue (2,2) and (3,3). Pop (2,2) — equal, enqueue two (None,None) pairs. Pop (3,3) — equal, enqueue two more. The four (None,None) pairs each hit continue. Queue empties → True.

Complexity: O(min(n, m)) time, O(w) space where w is the maximum number of simultaneous pairs (up to O(n) for a wide tree).

Common pitfalls

• Comparing values without shape: checking traversal value-sequences alone (inorder, preorder, …) accepts differently-shaped trees; nulls must participate in the comparison.
• Forgetting the both-None case: (None, None) is a match, not a failure — it must be checked before the one-sided None case.
• Using p.val == q.val as the whole answer at the root: equal roots say nothing about the subtrees; the recursion (or worklist) must descend.
• if not node vs if node is None: with plain TreeNodes these agree, but is None states the intent precisely and avoids surprises with falsy custom nodes.

Pattern takeaway

Structural equality of trees is the archetype of lockstep traversal: advance through two structures simultaneously, succeed on simultaneous exhaustion, fail on any disagreement. The same three-case skeleton (both None / one None / compare-and-recurse) reappears in Symmetric Tree (mirrored lockstep), Subtree of Another Tree (same-tree as a subroutine), and merging or diffing trees.