Invert Binary Tree
1Try it yourself first
Think for 20-30 minutes before you open any hint. Being stuck is where the learning happens.
Only for you, saved in this browser. After you see the approach you will compare it with your idea.2What is being asked
Flip a binary tree left-to-right: swap the left and right child of every node.
3Hint ladder
Take one rung at a time. Stop as soon as the idea clicks.
- Hint 1What would you do if the tree had only one node? And only a root with two leaves?
- Hint 2Swap the children, then repeat the same job on each child.
4The approach
Have you tried the hints? The approach is built as a path from the obvious way to the clever one.
Hold a family tree up to a mirror: every person's left and right children swap places, all the way down. A manager can do this without seeing the whole company: she swaps her own two teams, then tells each team leader "mirror your own teams too". The job spreads downward by itself.
- The obvious way
There is no "slow" version: every node must be touched once. The question is just how to organise it.
- The key insight
Inverting a tree = swap the two children, then invert each of them. The recursion bottoms out at an empty spot (nothing to do). Every node is visited once, so O(n).
- The algorithm
- Nothing here (empty)? Return nothing.
- Swap the left child and the right child.
- Invert the left subtree and the right subtree the same way.
- Return this node.
Watch it run
Exampletree = [4, 2, 7, 1, 3, 6, 9]
At the root 4: swap its two children, 2 and 7.
root 4: left 7, right 2
Where people slip
- If you swap first and then recurse on the original names you may invert a subtree twice; swap and recurse consistently.
How close was your idea?
You did not write an idea, and that is fine.
Be honest with yourself. This sets your revision list.
5Code
Try writing it yourself from the steps first. Then compare.
# TreeNode (val, left, right) is provided
def invert_tree(root):
if root is None:
return None
root.left, root.right = invert_tree(root.right), invert_tree(root.left) # swap the mirrored children
return rootNow close this and write it again from memory, in the language you will use in the interview. Reattempt after 1 day, 7 days and about 30 days.
6Still stuck? Watch a video
Seeing someone explain it out loud can make it click. Try the video after you have read the approach above.