Same Tree LeetCode Solution: Recursive and BFS Approaches

Same tree leetcode problem #100 is the most fundamental tree comparison question you will encounter. Given two binary trees, determine whether they are structurally identical and contain the same values at every corresponding node. If both conditions hold, the trees are the same — otherwise they are not.

This problem sits at the easy tier for good reason: it distills tree recursion down to its simplest form. But do not let the difficulty rating fool you. The dual-recursion pattern you learn here — comparing two tree pointers simultaneously — is the exact skeleton behind Symmetric Tree (#101), Subtree of Another Tree (#572), and Merge Two Binary Trees (#617).

Solving Same Tree cleanly means you already have the mental model for an entire family of tree comparison problems. That makes it one of the highest-leverage easy problems on LeetCode.

You are given the roots of two binary trees, p and q. Return true if they are the same tree, and false otherwise. Two binary trees are considered the same if they are structurally identical and every corresponding node has the same value.

The constraint is straightforward: both trees can have between 0 and 100 nodes, and node values range from -10,000 to 10,000. The function signature is isSameTree(p, q) where p and q are TreeNode or null.

The key insight is that "same tree" means both structure AND values must match. Two trees with identical values arranged in different structures are not the same tree. This distinction trips up beginners who focus only on values.

The recursive approach is the cleanest way to solve same tree leetcode #100. It uses exactly four cases that map directly to the problem definition. This four-case pattern is the core template for all tree comparison problems.

Case 1: Both nodes are null — you have reached the end of both trees simultaneously, so they match. Return true. Case 2: One node is null but the other is not — the trees have different structures. Return false. Case 3: Both nodes exist but their values differ — return false. Case 4: Both nodes exist and their values match — recurse on the left children AND the right children. Both recursive calls must return true.

The implementation is remarkably concise. In Python it is four lines, in JavaScript it is equally short. The time complexity is O(n) where n is the number of nodes in the smaller tree, because you visit each node at most once. Space complexity is O(h) where h is the height of the tree, due to the recursion stack — O(log n) for balanced trees, O(n) for skewed trees.

If you prefer an iterative approach, same tree BFS uses two queues (or a single queue of pairs) to traverse both trees level by level. At each step you dequeue one node from each queue, compare them, and enqueue their children as pairs.

Initialize both queues with the root nodes. While neither queue is empty, dequeue the front node from each. Apply the same four cases: both null means skip, one null means return false, values differ means return false, otherwise enqueue left-left and right-right child pairs. If you exhaust both queues without a mismatch, the trees are the same.

The BFS approach has the same O(n) time complexity. Space complexity is O(w) where w is the maximum width of the tree — which can be up to n/2 for a complete binary tree. In practice, the recursive DFS solution is preferred for its clarity and brevity, but BFS is worth knowing for interview follow-up questions.

Consider two trees that are the same: p = [1, 2, 3] and q = [1, 2, 3]. The recursion starts at roots (1, 1) — values match, so recurse. Left children (2, 2) — values match, recurse. Their children are all null pairs — return true. Right children (3, 3) — same logic. Every path returns true, so the final answer is true.

Now consider p = [1, 2] and q = [1, null, 2]. At the root (1, 1), values match. Left children: p has node 2 but q has null — one is null and the other is not. Return false immediately. You never even need to check the right subtrees.

This early termination is a key feature of the algorithm. The moment you find any mismatch — structural or value-based — you short-circuit and return false. This makes the average case faster than the worst case for trees that differ.

Both trees empty (p = null, q = null) is the simplest case and should return true. This is handled by the first base case in both the recursive and iterative solutions. One tree empty and the other non-empty should return false — handled by the second case.

Single-node trees with the same value (p = [1], q = [1]) return true. Single-node trees with different values (p = [1], q = [2]) return false. These cases verify that your base conditions and value comparison work independently.

A subtle edge case is trees with identical values but different shapes — for example, p = [1, 2, 3] versus q = [1, 3, 2]. These have the same set of values but different structures, so they are NOT the same tree. Your solution handles this automatically because you compare left-to-left and right-to-right, never cross-matching.

Same tree leetcode #100 introduces the dual-tree recursion pattern: two pointers walking two trees in lockstep. Once you internalize this pattern, Symmetric Tree (#101) becomes trivial — instead of comparing left-left and right-right, you compare left-right and right-left. Subtree of Another Tree (#572) nests a Same Tree check inside a single-tree traversal.

The four-case comparison template (both null, one null, values differ, recurse) is a building block you will use repeatedly. It appears in Merge Two Binary Trees (#617), Flip Equivalent Binary Trees (#951), and any problem that asks you to walk two trees simultaneously.

If you are preparing for coding interviews, drill this pattern with YeetCode flashcards until the four cases are automatic. When an interviewer hands you a tree comparison variant, you should be writing the base cases before they finish explaining the problem.