Are two binary trees identical? Compare the two roots, then trust recursion to compare the left pair and the right pair. A mismatch anywhere ends it.
▼The problem
LeetCode 100 (Easy). Given the roots of two binary trees p and q, return true if they are the same tree: the same shape, with equal values in every matching node.
Examples (LeetCode's): p = [1,2,3], q = [1,2,3] → true; p = [1,2], q = [1,null,2] → false (the 2 is a left child in p and a right child in q: different shapes); p = [1,2,1], q = [1,1,2] → false (same shape, different values).
The solution
def isSameTree(p, q):
if not p and not q:
return True
if not p or not q or p.val != q.val:
return False
return (isSameTree(p.left, q.left) and
isSameTree(p.right, q.right))Transcript
Same Tree. You get the roots of two binary trees, p and q. Return true if they are the same: same shape, same value in every spot.
One, two, three against one, two, three: identical, so true. One with a left child two, against one with a right child two: different shapes, so false. One, two, one against one, one, two: same shape, different values. False.
A tempting shortcut: write each tree out as a list and compare. But skip the empty spots, and both of those shape twins come out as one, two. You need null markers, or a direct walk.
Walk both trees in lockstep. If both spots are empty, they match. If only one is empty, or the values differ, it's false. Otherwise compare the left subtrees, then the right subtrees. The first mismatch stops everything.
In code: both null, return true. One null, or different values, return false. Then return the left check and the right check.
Take example one. One equals one. Go left: two equals two, and its children are both empty: true. Go right: three equals three. Every spot matched: true. Now one, two, one against one, one, two. The roots match, but on the left, two meets one. False, and the right side is never visited.
Each pair of nodes is checked once: order n time. The recursion goes as deep as the tree: order h space. Subtree of Another Tree reuses this check at every node.
Both empty, match. One empty or different, stop. Otherwise, check both sides. That's Same Tree.