Same Tree: Structural Equality by Parallel DFS

"Same Tree" is a Easy-level staple in Google, Amazon, LinkedIn loops, and it is a textbook fit for the Tree DFS pattern — one of the nine patterns that cover the bulk of what FAANG coding interviews actually test. Part 2 of 11 in the Tree DFS arc.

The Problem

Given two binary trees, return whether they are structurally identical with equal values. The entire solution is base-case discipline: both empty (True), one empty (False), values differ (False), else recurse on both child pairs.

Input:  p = [1, 2, 3], q = [1, 2, 3]
Output: True
p = [1, 2] vs q = [1, None, 2] is False — same values, different shape.

Recognizing the Tree DFS Pattern

Depth-first search commits to one branch before trying siblings — recursion (or an explicit stack) whose call structure mirrors the tree itself. Its natural questions are about paths (root to leaf), subtree properties (computed bottom-up from children), and exhaustive exploration (islands, connected regions). The recurring design decision is what each recursive call returns versus what it accumulates in shared state.

Comparing two structures node-by-node is parallel DFS — one traversal advancing through both trees simultaneously. Any structural comparison (equality, mirror symmetry, subtree containment) is this walk with a different comparison at each step.

The Approach

Order the base cases so each line can assume the previous ones failed: both None first, then either None, then value inequality, then the conjunction of child recursions. Four lines, each earning its position.

The iterative version pushes node pairs onto one stack — worth knowing because the same pair-stack idea powers Symmetric Tree and makes the recursion-ban follow-up trivial.

Python Solution

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


def is_same_tree(p: TreeNode | None, q: TreeNode | None) -> bool:
    """True if p and q have identical structure and values."""
    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 is_same_tree(p.left, q.left) and is_same_tree(p.right, q.right)

Complexity

• Time: O(min(n, m)) — the walk stops at the first structural or value mismatch
• Space: O(min(h1, h2)) — parallel recursion depth

Interview Tips and Follow-Ups

• Short-circuiting matters: and skips the right subtree once the left fails — name it when asked why the bound is min, not sum.
• Serializing both trees and comparing strings is a valid alternative with real pitfalls (None markers required) — discuss only if raised.
• Symmetric Tree is this function with one recursion mirrored (left vs right) — prepare them as a pair.

If this clicked, continue the Tree DFS arc in the Technical Interview category. One hundred questions, nine patterns, all in Python.