Same Tree
EasyTrees
Given the roots of two binary trees, p and q, return true if they are the same tree, and false otherwise. Two trees are the same when they have the same shape and every pair of matching nodes holds the same value.
On this page a tree is written in level order, top to bottom and left to right, with null where a child is missing: [6, 3, 8, 1] is 6 with children 3 and 8, and 3 with a left child 1.
Examples
Input: p = [5, 1, 9], q = [5, 1, 9] Output: true
Same shape, same values in the same places.
Input: p = [5, 1], q = [5, null, 1] Output: false
Both hold 5 and 1, but 1 is a left child in one tree and a right child in the other.
Constraints
- Each tree has 0 to 100 nodes.
-10⁴ ≤ node.val ≤ 10⁴
Stuck?
Hint 1
Two trees match when their roots hold the same value, their left subtrees match, and their right subtrees match.
Hint 2
Deal with missing nodes first: both missing is a match, only one missing is not. Then compare the values and recurse on both sides.
The idea
Two trees are the same when their roots match, their left subtrees are the same and their right subtrees are the same. Walk both trees together, node against node, and stop at the first difference in shape or value.
Time O(n)Extra space O(h) for a tree of height h
Try it again with the idea in mind, or go through the code one step at a time.
The code, step by step
Step 1 of 3
Two empty trees are the same. Each branch of the recursion ends here when the shapes agree.
function isSameTree(p, q) { if (!p && !q) return true; if (!p || !q || p.val !== q.val) return false; return isSameTree(p.left, q.left) && isSameTree(p.right, q.right);}The trap
Listing each tree's values in preorder and comparing the lists forgets where the children are missing. A node with only a left child and a node with only a right child give the same list, so two trees of different shapes compare as equal. It looks right because trees of the same shape with different values are still caught.
function isSameTree(p, q) { // compares the preorder values, but without marking missing children const values = (node, out = []) => { if (node) { out.push(node.val); values(node.left, out); values(node.right, out); } return out; }; return values(p).join(',') === values(q).join(',');}