Same Tree

Problem Statement

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.

Examples

Example 1

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

Tree p:     Tree q:
    1           1
   / \         / \
  2   3       2   3

Both trees are identical

Example 2

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

Tree p:     Tree q:
    1           1
   /             \
  2               2

Different structure

Example 3

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

Tree p:     Tree q:
    1           1
   / \         / \
  2   1       1   2

Different values in children

Intuition

Two trees are the same if:

1. Both roots have the same value
2. Left subtrees are the same
3. Right subtrees are the same

This is a perfect fit for recursion with simultaneous traversal.

Pattern Recognition

This is a Tree Comparison problem with:

• Simultaneous DFS on both trees
• Pre-order traversal (check root first)
• Base cases for null nodes

Approach

Recursive DFS

1. Base Cases:

   • If both nodes are null → trees are the same (return true)
   • If one is null and other isn't → trees are different (return false)
   • If values differ → trees are different (return false)

2. Recursive Case:

   • Check if left subtrees are the same
   • Check if right subtrees are the same
   • Return true only if both are true

Why this works:

• We check every corresponding pair of nodes
• Base cases handle all edge scenarios
• Recursion naturally handles the tree structure

Implementation Pattern

isSameTree(p, q):
  if not p and not q: return True
  if not p or not q: return False
  if p.val != q.val: return False
  return isSameTree(p.left, q.left) and isSameTree(p.right, q.right)

Edge Cases

• Both trees empty → same
• One tree empty, one not → different
• Same structure, different values
• Different structure, same values
• Single node trees

Complexity Analysis

• Time: O(min(n, m)) where n, m = number of nodes in each tree

  • Visit nodes until we find a difference
  • Worst case: visit all nodes in smaller tree
  • If trees are identical: O(n)

• Space: O(min(h₁, h₂)) where h₁, h₂ = heights

  • Recursion call stack
  • O(log n) for balanced trees
  • O(n) for skewed trees