Skip to main content

100 - Same Tree

Difficulty: Easy | Pattern: Tree DFS / BFS | Company tags: Amazon, Bloomberg, LinkedIn

Problem Statement​

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

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

Algorithm Flow​

Approach: Recursive DFS — O(n)​

Key insight: Two trees are the same if both are None (base case True), one is None and the other is not (False), or their values are equal AND both subtrees are the same.

def isSameTree(p, q) -> bool:
    if not p and not q:
        return True
    if not p or not q:
        return False
    return p.val == q.val and isSameTree(p.left, q.left) and isSameTree(p.right, q.right)

Iterative BFS​

from collections import deque

def isSameTree(p, q) -> bool:
    queue = deque([(p, q)])
    while queue:
        node1, node2 = queue.popleft()
        if not node1 and not node2:
            continue
        if not node1 or not node2:
            return False
        if node1.val != node2.val:
            return False
        queue.append((node1.left, node2.left))
        queue.append((node1.right, node2.right))
    return True

Dry Run​

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

isSameTree(1,1): vals equal, recurse left and right
  isSameTree(2,2): vals equal, both leaves → True
  isSameTree(3,3): vals equal, both leaves → True
→ True

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

isSameTree(1,1): vals equal, recurse left
  isSameTree(2, None): one None, other not → False

Edge Cases​

  • Both empty → True
  • One empty → False
  • Same values different structure → False

Complexity​

  • Time: O(n)
  • Space: O(h) — O(log n) balanced, O(n) skewed

Related: LeetCode 572 (Subtree of Another Tree) uses isSameTree as a helper.

Key Terms​

TermDefinition
RecursionSolving a problem by calling the same function on smaller subproblems (here, subtrees).
Base caseThe terminal condition that stops recursion — here, when one or both nodes are null.
DFS (Depth-First Search)Traversal that goes as deep as possible down one branch before backtracking; used in the recursive solution.
BFS (Breadth-First Search)Traversal that processes nodes level by level using a queue; used in the iterative solution.
Structural equalityTwo trees match only if their shapes and node values are identical, not just their value sets.

FAQ​

Q: Can this be solved without extra space (beyond recursion stack)? A: The recursive DFS uses O(h) stack space, which is unavoidable unless you flatten both trees to sequences first (which costs O(n) space instead).

Q: What happens if both trees are empty? A: Both p and q are None, the first check not p and not q is true, and the function returns True.

Q: Why check not p or not q separately from value comparison? A: Because comparing p.val when p is None raises an AttributeError. The null check must happen before dereferencing.

Q: How would you extend this to check if two trees are mirror images (symmetric)? A: Compare p.left with q.right and p.right with q.left instead of same-side children — this is the core idea behind LeetCode 101 (Symmetric Tree).

Q: Recursive vs iterative — which is better in an interview? A: Recursive is cleaner and easier to explain; mention the iterative BFS/stack version if asked to avoid recursion or discuss stack overflow risk on deep trees.

Quick Revision​

  • Two trees are the same if they have identical structure AND identical node values at every position.
  • Base cases: both null → True; exactly one null → False.
  • Recursive step: p.val == q.val and isSameTree(p.left, q.left) and isSameTree(p.right, q.right).
  • Iterative version replaces recursion with a queue (BFS) or stack (DFS), pushing pairs of nodes.
  • Time complexity: O(n) — every node pair is visited once.
  • Space complexity: O(h) for recursion stack; O(w) for BFS queue.
  • Short-circuit evaluation (and) skips unnecessary recursive calls once a mismatch is found.
  • This same-comparison logic is a building block for Subtree of Another Tree (LC 572).
  • 102 - Binary Tree Level Order Traversal — same BFS/queue traversal pattern applied to level grouping.
  • 104 - Maximum Depth of Binary Tree — same recursive tree DFS pattern computing a scalar from subtrees.
  • Symmetric Tree (pattern: recursive tree comparison with mirrored children) — LeetCode 101, not in this directory.
  • Subtree of Another Tree (pattern: reuses isSameTree as a helper at every node) — LeetCode 572, not in this directory.