1
a.val
Two binary trees are the same when they have identical structure and identical values. Walk both in lockstep with a single recursive DFS — compare the node pair, then the left subtrees, then the right.
Given the roots of two binary trees p and q, return true only if they are structurally identical and every corresponding node holds the same value. p=[1,2,3], q=[1,2,3] → true. p=[1,2], q=[1,null,2] → false (the 2 hangs on different sides).
p and q are both null, this branch ends in agreement → return true.null, the shapes diverge → return false. This is the structural check.p.val !== q.val, the trees disagree here → return false.left subtrees match and right subtrees match.p.left with q.left and p.right with q.right — never cross them. Same values in a different shape (e.g. a left child vs a right child) is notthe same tree, which is exactly why the "exactly one null" check matters.Time is O(n) where nis the smaller tree's size (we stop at the first mismatch). Space is O(h) for the call stack — O(log n) balanced, O(n) for a degenerate (linked-list) tree. An iterative version uses an explicit stack/queue of node pairs with the same bounds.
left.left with right.right), Subtree of Another Tree (run isSameTree at every node), and Merge Two Binary Trees.class TreeNode {
val: number;
left: TreeNode | null;
right: TreeNode | null;
constructor(val = 0, left: TreeNode | null = null, right: TreeNode | null = null) {
this.val = val;
this.left = left;
this.right = right;
}
}
function isSameTree(p: TreeNode | null, q: TreeNode | null): boolean {
// Both empty here -> this branch matches.
if (p === null && q === null) return true;
// Exactly one empty -> shapes differ.
if (p === null || q === null) return false;
// Values differ at this node -> not the same.
if (p.val !== q.val) return false;
// Node matches; both subtrees must match too.
return isSameTree(p.left, q.left) && isSameTree(p.right, q.right);
}null on both sides at the same time means the branches ended together. Return true so the parent's && stays alive.false immediately. This single line is the entire structural comparison.p.val !== q.val they disagree right here, so short-circuit to false without descending.&& short-circuits — the moment any pair fails, recursion unwinds with false.(p, q) onto a stack; pop, apply the same null/value checks, then push (p.left, q.left) and (p.right, q.right).a.left with b.right and a.right with b.left.s; at each node run isSameTree(node, t). Total O(n·m).| "are these two trees identical?" | synchronized DFS on the pair |
| compare structure AND values | both-null / one-null / val checks |
| "mirror / symmetric" | same skeleton, swap left↔right |
| "is X a subtree of Y?" | isSameTree at every node of Y |
function isSameTree(p: TreeNode | null, q: TreeNode | null): boolean {
if (p === null && q === null) return true; // both empty -> equal
if (p === null || q === null) return false; // one empty -> differ
if (p.val !== q.val) return false; // value mismatch
return isSameTree(p.left, q.left) // recurse left
&& isSameTree(p.right, q.right); // and right
}