Same Tree

Two trees match only if their roots match and both pairs of children match, recursively — a direct fit for DFS. A BFS walking both trees in lockstep works identically well; both are O(n), they just trade a stack for a queue.

Recursive (DFS)

OptimalTime O(n)Space O(h)

If both nodes are None, they match. If only one is None, or their values differ, they cannot match. Otherwise recurse into both left and both right children.

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

class Solution:
    def isSameTree(self, p: TreeNode | None, q: TreeNode | None) -> 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)

Watch the two trees advance in lockstep on the first example p = [1,2,3], q = [1,2,3]: each recursive call compares one corresponding pair, and a pair of missing children already counts as a match.

current pair1vs1both exist

1 / 13

currentcomparingresult

Start at the roots: both nodes exist, so the first test is their values.

Walk p = [1,2,1] and q = [1,1,2] a pair at a time. The roots both hold 1, so the first check passes and recursion reaches the children. But at the second level p.left = 2 while q.left = 1 — the values differ, so isSameTree(p.left, q.left) returns False and the right subtrees are never compared. The trees are not the same.

Complexity: in the worst case (both trees identical) every node pair is visited once → O(n) time, where n is the smaller tree’s size (a mismatch short-circuits early). Recursion depth → O(h) space.

Iterative (BFS with paired queue)

Time O(n)Space O(n)

Push corresponding node pairs onto a queue instead of recursing, comparing each pair as it is popped. Useful when recursion depth is a concern.

from collections import deque

class Solution:
    def isSameTree(self, p: TreeNode | None, q: TreeNode | None) -> bool:
        queue = deque([(p, q)])
        while queue:
            node_p, node_q = queue.popleft()
            if node_p is None and node_q is None:
                continue
            if node_p is None or node_q is None or node_p.val != node_q.val:
                return False
            queue.append((node_p.left, node_q.left))
            queue.append((node_p.right, node_q.right))
        return True

Why prefer this: identical O(n) time, but no recursion — safe for very deep, unbalanced trees where the DFS call stack could overflow. Space becomes the queue’s peak width, O(n) worst case, versus O(h) for the recursive version, so it is a robustness tradeoff rather than a performance win.

Recursive (DFS)

Iterative (BFS with paired queue)

More Trees practice