Flip Every Branch
EasyTrees
Problem
A UI toolkit stores a right-to-left layout as a binary tree. To produce the left-to-right layout it must swap the left and right child of every node.
Given the root, mirror the tree in place and return its root.
Example 1
- Input:
- root = [4, 2, 7, 1, 3, 6, 9]
- Output:
- [4, 7, 2, 9, 6, 3, 1]
Example 2
- Input:
- root = [1, 2]
- Output:
- [1, null, 2]
The lone left child moves to the right.
Constraints
- 0 ≤ number of nodes ≤ 10^4
- -100 ≤ node.val ≤ 100
Hint
Show the first hint
Mirroring the whole tree is the same as doing one tiny operation at every node.
Walkthrough
How to approach it
01Clarify before coding
- In place or a new tree? In place; returning the same root object is fine.
- Empty tree? Return it as is (null).
- Do values change? No, only child pointers.
02Brute force
Build a brand-new mirrored tree by recursion and return it.
Cost: O(n) time but O(n) extra nodes, and recursion depth can reach 10^4.
The rest of the walkthrough is in the app
The full walkthrough (key insight, step-by-step, dry run, complexity, edge cases, pitfalls, follow-ups) and solutions in Python and JavaScript are in the app, next to an editor and a terminal that runs your code against the tests.
This problem is part of Pro.