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 tiny bound means any O(n) traversal is fine — the problem is about getting the structural comparison right, not about 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

The naive idea: flatten each tree to a string with a traversal, then compare strings. A plain preorder of values is wrong (Example 2’s trees both give “1,2”), so null children must be recorded explicitly to pin down 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


class Solution:
    def isSameTree(self, 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 works, but it walks both trees fully even when they differ at the root, and building strings just to compare structures is roundabout — comparing the trees node-by-node is simpler and can stop at the first mismatch.

Approach 2 — Recursive parallel DFS

The insight: two trees are identical iff their roots agree and 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 fail fast on 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


class Solution:
    def isSameTree(self, 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 self.isSameTree(p.left, q.left) and self.isSameTree(p.right, q.right)

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 insight: the recursion compares independent pairs of nodes, so any worklist of pairs — stack or queue — does the same job without recursion. This is breadth-first search (BFS): process node pairs level by level using a FIFO queue.

# 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


class Solution:
    def isSameTree(self, 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.