Will the Mobile Hang Straight
A toy maker builds hanging mobiles for babies' rooms. Each charm hangs from a hook, and from each charm up to two arms reach out, a left arm and a right arm, each holding another charm. The toy maker records a mobile as a binary tree of charm weights in grams.
A mobile hangs straight only if its two halves are mirror images: the left half, seen in a mirror, matches the right half charm for charm and arm for arm. The toy maker wants a quick check before gluing anything.
Your task
Write hangsStraight(root). Return true if the tree is a mirror image of itself around its centre line, and false otherwise. The weights must match as well as the shape.
An empty mobile counts as straight. Trees are shown in level order, like [6, 2, 2, 4, 9, 9, 4], where null marks a missing child. Your function receives real TreeNode objects with val, left and right.
hangsStraight(root: TreeNode) → bool
Examples
root = [6, 2, 2, 4, 9, 9, 4]
true
Under the 6 there is a 2 on each side. The left 2 holds 4 then 9. The right 2 holds 9 then 4. In a mirror, the outer charms (4 and 4) face each other and the inner charms (9 and 9) face each other, so it hangs straight.
root = [6, 2, 2, null, 4, null, 4]
false
Both 2s hold a 4 on their right arm. The two halves are identical copies, not mirror images: the left 4 is on the inside, the right 4 is on the outside. The mobile tips.
Constraints
- 0 ≤ number of charms ≤ 1,000
- 1 ≤ weight ≤ 1,000
- The tree is at most 500 levels deep.
Start with brute force
Make a mirrored copy of the whole tree, then compare the copy with the original node by node. It is correct and O(n), but it builds a second tree of n nodes just to throw it away.
A tempting shortcut is wrong: checking that each level's weights read the same forwards and backwards. The second example has levels 6, then 2 2, then 4 4, which all look fine, but the 4s hang on the wrong arms. Missing children matter, and comparing the two halves directly takes care of them.
Hints
0 of 4 shown- Hint 1
In the first example, the left 2 and the right 2 match. Which charm under the left 2 must match the 4 on the far right?
- Hint 2
The outermost charms pair up, and the innermost charms pair up. So the left child of one side is compared with the right child of the other side.
- Hint 3
Write a helper that takes two subtrees and answers: are these mirror images of each other? What must be true about their values, and which pairs of children does it need to check next?
- Hint 4
mirror(a, b): both null gives true, one null gives false. Otherwisea.val === b.valandmirror(a.left, b.right)andmirror(a.right, b.left). The answer ismirror(root.left, root.right).
Walkthrough and solution
Unlocks when you pass every test. Stuck for a while? Looking is fine too, as long as you then close it and write the code yourself.
How to solve it
Symmetry is a question about pairs of subtrees, not about one subtree. So compare the two halves against each other, crossing over at every step: outer with outer, inner with inner.
Trace [6, 2, 2, 4, 9, 9, 4]:
mirror(left 2, right 2): both weigh 2. Now check the outer pair and the inner pair.- Outer pair: left 2's left child (4) with right 2's right child (4). Equal, and both have no children, so true.
- Inner pair: left 2's right child (9) with right 2's left child (9). Equal, no children, true.
Everything matched, so the mobile hangs straight. On the second example the outer pair is (null, 4): exactly one is missing, so the answer is false right away.
function hangsStraight(root) {
// Are subtrees a and b mirror images of each other?
function mirror(a, b) {
if (a === null && b === null) return true;
if (a === null || b === null) return false;
return a.val === b.val
&& mirror(a.left, b.right) // outer pair
&& mirror(a.right, b.left); // inner pair
}
return root === null || mirror(root.left, root.right);
}def hangs_straight(root):
# Are subtrees a and b mirror images of each other?
def mirror(a, b):
if a is None and b is None:
return True
if a is None or b is None:
return False
return (a.val == b.val
and mirror(a.left, b.right) # outer pair
and mirror(a.right, b.left)) # inner pair
return root is None or mirror(root.left, root.right)Run your code to see results here. Run checks the examples. Submit checks every test, including hidden edge cases.