Same Tree: two trees, one recursive question

Two binary trees are the same if and only if every corresponding pair of nodes has the same value and the same structural position. That is it. The problem is asking you to walk both trees in lockstep and fail the moment anything diverges — a null where there should be a value, a value that does not match, a child that exists in one tree but not the other.

The structural reading is immediate: the answer for isSameTree(p, q) is true if the current nodes are equal and isSameTree(p.left, q.left) and isSameTree(p.right, q.right) both return true. That recursion terminates at null nodes. The implementation nearly writes itself.

What the constraints tell you before you write a line

The problem bounds are [0, 100] nodes and values in [-10⁴, 10⁴]. Neither bound demands any cleverness.

100 nodes means you can recurse without worrying about stack overflow — Python's default recursion limit is 1000, and the maximum possible call depth here is 100 (a fully left-skewed or right-skewed chain). There is no case within these bounds where you are forced to go iterative to avoid crashing. The BFS solution is not about safety; it is an alternative traversal strategy.

The value range [-10⁴, 10⁴] includes negatives and zero, which matters only because it rules out treating 0 as a sentinel. Always compare p.val != q.val directly — never assume 0 means empty.

The zero-node case (n = 0) is explicitly in range. Both trees can be null. That is not an edge case to handle awkwardly; it falls cleanly out of the first base case.

Approach 1: Recursive DFS — three base cases, then recurse

The recursive version is as short as a tree problem gets.

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

public class Solution {
    public bool IsSameTree(TreeNode p, TreeNode q) {
        if (p == null && q == null) return true;
        if (p == null || q == null) return false;
        if (p.val != q.val) return false;
        return IsSameTree(p.left, q.left) && IsSameTree(p.right, q.right);
    }
}

The base cases matter in order. Check both-null first — that is the success termination condition. Then check one-null — structural mismatch. Then check values. If you put the value check before the null checks, you will dereference null on the structural mismatch case.

Short-circuit evaluation does real work in the recursive call. Once isSameTree(p.left, q.left) returns false, Python's and / C#'s && does not evaluate the right subtree at all. You get early exit for free.

Hand trace through Example 2: p = [1,2], q = [1,null,2]

Call isSameTree(p=1, q=1):

• Both non-null, values equal (1 == 1) -> recurse into children
• Call isSameTree(p=2, q=null):
  • p is non-null, q is null -> second base case fires, return false
• Left subtree returned false, and short-circuits
• Final result: false

The tree shapes are different: p has a left child, q does not. The structural divergence surfaces immediately at the left subtree call.

Time and space complexity

Time: O(min(m, n)) where m and n are the node counts of the two trees. In the worst case (identical trees), you visit every node in the smaller tree. As soon as any pair diverges, you stop — worst case is still O(min(m, n)), but you often do less.

Space: O(min(m, n)) for the call stack in the worst case. A completely skewed chain of 100 nodes gives 100 stack frames. A balanced tree of 100 nodes is at most 7 frames deep. In practice, the space footprint is determined by tree height, not node count.

Approach 2: Iterative BFS — a shared queue for two trees

Instead of recursion, you can process both trees simultaneously using a queue. Each queue entry holds a pair (node_from_p, node_from_q). You dequeue a pair, validate it, then enqueue both pairs of children.

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

using System.Collections.Generic;
 
public class Solution {
    public bool IsSameTree(TreeNode p, TreeNode q) {
        var queue = new Queue<(TreeNode, TreeNode)>();
        queue.Enqueue((p, q));
        while (queue.Count > 0) {
            var (node1, node2) = queue.Dequeue();
            if (node1 == null && node2 == null) continue;
            if (node1 == null || node2 == null || node1.val != node2.val) return false;
            queue.Enqueue((node1.left, node2.left));
            queue.Enqueue((node1.right, node2.right));
        }
        return true;
    }
}

The continue on the both-null case is deliberate. Null-null pairs are valid leaf boundaries — you enqueue them (since you always push both children), then skip past them when dequeued. An alternative is to guard the enqueue with null checks, but that makes the condition slightly harder to read.

Tracing Example 1: p = [1,2,3], q = [1,2,3]

Initial:  queue = [(1,1)]

Dequeue (1,1): both non-null, values match (1==1)
  -> enqueue (2,2), (3,3)
  queue = [(2,2), (3,3)]

Dequeue (2,2): both non-null, values match (2==2)
  -> enqueue (null,null), (null,null)
  queue = [(3,3), (null,null), (null,null)]

Dequeue (3,3): both non-null, values match (3==3)
  -> enqueue (null,null), (null,null)
  queue = [(null,null), (null,null), (null,null), (null,null)]

Dequeue (null,null): both null -> continue
Dequeue (null,null): both null -> continue
Dequeue (null,null): both null -> continue
Dequeue (null,null): both null -> continue

queue empty -> return true

Every node visited once. The null pairs cost a dequeue and a continue each — they add O(n) work in aggregate, but do not change the asymptotic bound.

Time and space complexity

Time: O(min(m, n)), same argument as DFS. You process pairs until divergence or exhaustion.

Space: O(min(m, n)) for the queue. At the widest level of a balanced tree, the queue holds about n/2 pairs. For a skewed chain, the queue never holds more than one pair at a time. In the worst case for BFS (perfectly balanced tree), space is O(n). In the worst case for DFS (skewed chain), space is also O(n). The constants differ, but the O class is the same.

Edge cases, worked out

Both trees null (p = null, q = null): in DFS, the first base case fires immediately and returns true. In BFS, the initial enqueue puts (null, null) in the queue, the dequeue hits the both-null check, and continue drains the queue; the while exits and you return true. Both correct.

One tree null (p = [1], q = null): DFS hits base case two — one is non-null, one is null — and returns false. BFS dequeues (node_1, null), hits the single-null branch, returns false. One call in either case.

Structurally different trees with same values: p = [1,2], q = [1,null,2] is Example 2. Both trees have nodes valued 1 and 2, but the 2 is a left child in p and a right child in q. The value check passes at the root. At the left subtree, p.left = 2 and q.left = null diverges immediately. The algorithm does not need to see q.right to know the answer.

Trees with only one node: p = [5], q = [5]. DFS recurses into isSameTree(null, null) twice and hits base case one both times. Returns true. No surprises.

Negative and zero values: p.val = -104 and q.val = 0 will correctly compare as unequal. The comparison is exact; there is no special handling needed for the value range.

Which approach to write, and when

I reach for the DFS version immediately. The recursive structure matches the recursive definition of the problem: two trees are the same if their roots match and their subtrees are the same. The code is a near-literal transcription of that definition. Anyone reading it can verify it in ten seconds.

The BFS version is worth knowing, but not because it is faster or uses less memory — it does not. The reason to know it is that sometimes you need to process both trees level by level, and building the pattern of "shared queue with node pairs" in your head is useful for problems where BFS is genuinely required (level-order comparison, for instance). Same Tree is a good place to see the technique in a simple setting.

The stack overflow argument — usually cited for choosing BFS — does not apply here. 100 nodes, max 100 stack frames. That concern is real for n = 10⁵, not n = 100.

Comparison table

The complexity is identical. This is not a "which is faster" question. It is a "which is clearer" question, and the recursive version wins on this problem.

Where this fits in the trees series

This is problem four in the series, after Maximum Depth of Binary Tree (104), Invert Binary Tree (226), and Binary Tree Level Order Traversal (102). Those three established the main traversal patterns — DFS recursion on a single tree, BFS with a queue. Same Tree is the first problem in the series that takes two trees as input. That is the conceptual step: instead of asking "what is true about this tree," you are asking "what is the relationship between these two trees."

The three base cases here — both null, one null, values differ — show up repeatedly in problems that compare or combine trees. Recognizing that pattern is the transferable skill.

Symmetric Tree (101) is the natural next question: instead of comparing two separate trees, check whether a single tree is its own mirror image. The recursion changes from isSameTree(p.left, q.left) and isSameTree(p.right, q.right) to comparing left.left against right.right and left.right against right.left — the same structural comparison, but cross-sided.

Subtree of Another Tree (572) extends Same Tree directly. You check whether any subtree of root is identical to subRoot. The implementation calls a helper that is essentially isSameTree at each candidate root. If this problem felt comfortable, 572 is the natural escalation.

Flip Equivalent Binary Trees (951) loosens the comparison: two trees are flip-equivalent if you can make them identical by swapping some children. The base cases are the same; the recursive case adds an or — check same-order and check swapped-order. Another instance of the "compare corresponding node pairs" pattern with a modified success condition.

Merge Two Binary Trees (617) is the construction counterpart. Instead of comparing two trees, you build a new tree by summing corresponding values. The traversal structure is identical; only the operation at each node changes.