DSAPrep
EasyTrees

Same Tree

Given the roots of two binary trees p and q, write a function to check if they are the same or not.

Two binary trees are considered the same if they are structurally identical, and the nodes have the same value.

Example 1

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

Example 2

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

Example 3

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

Constraints

  • The number of nodes in both trees is in the range [0, 100].
  • -10^4 <= Node.val <= 10^4
View original on LeetCode ↗

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)

Time 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)

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.