Why are two empty nodes considered the same?

Two missing children are identical subtrees: both have no nodes. That base case is what lets the recursion stop at the leaves and report a match.

What is the time and space complexity of Same Tree?

O(n) time, where n is the number of nodes in the smaller tree, because each pair is compared at most once. O(h) space for the recursion stack, where h is the tree height: O(log n) for a balanced tree and O(n) for a skewed one.

Can Same Tree be solved without recursion?

Yes. Push the pair (p, q) onto a stack or queue, pop pairs, apply the same checks, and push the left and right child pairs. The order of comparison changes; the answer does not.

Same Tree

Check whether two binary trees have the same shape and the same values by walking both in lockstep with DFS.

EasySolve on LeetCode

Problem Understanding

Same Tree: given the roots of two binary trees p and q, return true if they are structurally identical and every pair of corresponding nodes has the same value.

Examples: [1, 2, 3] and [1, 2, 3] are the same. [1, 2] and [1, null, 2] are not: node 2 is a left child in one and a right child in the other.

Attempt 1: Serialize and Compare

Write each tree out as a traversal string, including markers for empty children, and compare the strings. It works, but it builds two strings of size O(n) and always reads both trees completely, even when the roots already differ. Comparing node by node can stop at the first difference.

The Intuition: Walk Both Trees at Once

Two trees are the same exactly when their roots match and their left subtrees are the same and their right subtrees are the same. That definition is the recursion:

Both nodes empty: the same.
One empty, or different values: not the same.
Otherwise: compare the left pair, then the right pair.

Each call looks at the same position in both trees, so the two walks stay in lockstep.

Interactive Walkthrough

Tree p and tree q are drawn side by side and the pair being compared is marked in both. Subtrees turn green as they are confirmed identical; the first difference turns red, and a missing node shows a dashed null where its partner would be.

Dry Run Table

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

Call	`p` node	`q` node	Result
root	1	1	values equal, compare left
root.left	2	1	values differ: false
root	—	—	left differs: return false without checking the right

The right subtrees are never compared: the first difference decides the answer.

The Solution Template

Recursive DFS over both trees, stopping at the first difference.

Same Tree Code

1var isSameTree = function(p, q) {
2    if (!p && !q) {
3        return true;
4    }
5    if (!p || !q || p.val !== q.val) {
6        return false;
7    }
8    if (!isSameTree(p.left, q.left)) {
9        return false;
10    }
11    return isSameTree(p.right, q.right);
12};

Edge Cases & Common Mistakes

Both trees empty: the same, so return true.
Same values, different shape: [1, 2] and [1, null, 2] differ; comparing only the list of values would wrongly say they match.
Checking p.val before checking for null: reading .val on a missing node crashes. Test for empty nodes first.
Comparing only in-order traversals: different trees can share one, so shape has to be part of the comparison.

Summary

Same Tree is DFS on two trees at once: handle the empty cases, compare the values, then recurse left and right, stopping at the first difference. The same lockstep walk is the core of Subtree of Another Tree and of checking whether a tree is symmetric.

More practice: DSA interview questions with answers · patterns cheat sheet

Maximum Depth of Binary Tree

Balanced Binary Tree