Same Tree

Difficulty: Easy Source: NeetCode

Problem

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

Prerequisites

Before attempting this problem, you should be comfortable with:

• Binary Trees — Structure and traversal of tree nodes
• Recursion — Comparing two trees by comparing their subproblems
• Short-circuit Logic — Returning early when a mismatch is found

1. Recursive DFS

Intuition

Two trees are the same if: their roots have the same value, their left subtrees are the same, and their right subtrees are the same. This decomposes perfectly into recursion. The base cases handle structural differences: if both are null they match, if only one is null they don’t.

Algorithm

1. If both nodes are null → return true (both trees “end” here)
2. If exactly one is null → return false (structural mismatch)
3. If p.val != q.val → return false (value mismatch)
4. Return same_tree(p.left, q.left) and same_tree(p.right, q.right)

Solution

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

def is_same_tree(p, q):
    # Both null: they match at this position
    if not p and not q:
        return True
    # One null, one not: structure differs
    if not p or not q:
        return False
    # Values differ
    if p.val != q.val:
        return False
    # Recurse on both subtrees
    return is_same_tree(p.left, q.left) and is_same_tree(p.right, q.right)

# --- helpers ---
def build_tree(values):
    if not values:
        return None
    root = TreeNode(values[0])
    queue = [root]
    i = 1
    while queue and i < len(values):
        node = queue.pop(0)
        if i < len(values) and values[i] is not None:
            node.left = TreeNode(values[i])
            queue.append(node.left)
        i += 1
        if i < len(values) and values[i] is not None:
            node.right = TreeNode(values[i])
            queue.append(node.right)
        i += 1
    return root

# --- tests ---
p1 = build_tree([1, 2, 3])
q1 = build_tree([1, 2, 3])
print(is_same_tree(p1, q1))  # True

p2 = build_tree([1, 2])
q2 = build_tree([1, None, 2])
print(is_same_tree(p2, q2))  # False

p3 = build_tree([1, 2, 1])
q3 = build_tree([1, 1, 2])
print(is_same_tree(p3, q3))  # False

p4 = build_tree([])
q4 = build_tree([])
print(is_same_tree(p4, q4))  # True

Complexity

• Time: O(n) — at most n nodes visited where n = min(size(p), size(q))
• Space: O(h) — recursion stack depth proportional to tree height

2. Iterative (Stack-Based)

Intuition

We can do the same comparison without recursion by using a stack of node pairs. At each step, pop a pair and apply the same three checks as the recursive version.

Solution

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

def is_same_tree_iterative(p, q):
    stack = [(p, q)]

    while stack:
        node1, node2 = stack.pop()

        if not node1 and not node2:
            continue
        if not node1 or not node2:
            return False
        if node1.val != node2.val:
            return False

        stack.append((node1.left, node2.left))
        stack.append((node1.right, node2.right))

    return True

# --- helpers ---
def build_tree(values):
    if not values:
        return None
    root = TreeNode(values[0])
    queue = [root]
    i = 1
    while queue and i < len(values):
        node = queue.pop(0)
        if i < len(values) and values[i] is not None:
            node.left = TreeNode(values[i])
            queue.append(node.left)
        i += 1
        if i < len(values) and values[i] is not None:
            node.right = TreeNode(values[i])
            queue.append(node.right)
        i += 1
    return root

# --- tests ---
p1 = build_tree([1, 2, 3])
q1 = build_tree([1, 2, 3])
print(is_same_tree_iterative(p1, q1))  # True

p2 = build_tree([1, 2])
q2 = build_tree([1, None, 2])
print(is_same_tree_iterative(p2, q2))  # False

Complexity

• Time: O(n) — each node pair is processed once
• Space: O(h) — stack size proportional to tree height

Common Pitfalls

Checking only values, not structure. [1,2] and [1,null,2] have the same values but different structures. The null checks for structural equality must come before value comparison.

Short-circuiting too eagerly. The and in same_tree(left) and same_tree(right) already short-circuits — if the left subtrees differ, Python won’t even evaluate the right. This is efficient by default.