Invert Binary Tree
EasyTrees
Given the root of a binary tree, swap every node’s left and right children, all the way down, and return the root.
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: root = [6, 3, 8, 1, 4, 7, 9] Output: [6, 8, 3, 9, 7, 4, 1]
Every left and right child swap places, so each level reads backwards.
Input: root = [10, 5, 15] Output: [10, 15, 5]
The root’s two children swap.
Constraints
- The tree has 0 to 100 nodes.
-100 ≤ node.val ≤ 100
Stuck?
Hint 1
Inverting a tree is: swap the root’s two children, then invert each of them.
Hint 2
A queue works too, level by level, if you would rather not recurse.
The idea
A tree is inverted when its root's two children have traded places and each of those subtrees is inverted too. So every node needs exactly one swap, and a recursion that reaches every node once does the whole job.
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 4
An empty tree is already inverted. This is also where the recursion stops, below every leaf.
function invertTree(root) { if (!root) return null; const left = invertTree(root.left); const right = invertTree(root.right); root.left = right; root.right = left; return root;}The trap
Swapping the root's two children without recursing flips only the top level. On a tree of two levels that is the whole job, so it looks finished. With a third level, the two subtrees have changed sides but are still in their old order inside, so the levels below the second come out wrong.
function invertTree(root) { if (root) [root.left, root.right] = [root.right, root.left]; // only the top level return root;}