#226 Invert Binary Tree
frequently reported atGoogleAmazonBloombergMicrosoftMetaLinkedIn
the problem
In plain words
Mirror the tree: swap the left and right child of every node. Return the root.
in root = [4,2,7,1,3,6,9]
out [4,7,2,9,6,3,1]
in root = [2,1,3]
out [2,3,1]
in root = []
out []
- 0 ≤ number of nodes ≤ 100
- -100 ≤ Node.val ≤ 100
your turn
Try it before you peek
Read the examples, say the brute force out loud, then write code: here or on LeetCode ↗. Stuck for 20 minutes? Open one hint at a time.
Solve it in the browser
LeetCode-style: complete the class. Compiled by the real javac (Java 17) and judged right here — nothing is sent anywhere.
Solutions are hidden so you can try first. Even 20 minutes of real effort makes the answer stick far better than reading it.
Marking the problem solved, or opening every hint, also shows it.
the aha
Key insight
patternTree DFS (bottom-up)
Mirroring a tree = mirroring both subtrees and swapping them. Every node needs exactly one swap; the order you visit them in doesn't matter.
solutions
From brute force to optimal
Invert both subtrees, then swap them.
- null → null.
- left = invert(left), right = invert(right).
- root.left = right; root.right = left.
Each node is swapped once.
Recursion stack.
class Solution { public TreeNode invertTree(TreeNode root) { if (root == null) return null; TreeNode left = invertTree(root.left); // mirror both subtrees first… TreeNode right = invertTree(root.right); root.left = right; // …then swap them root.right = left; return root; }}Dry run
Visit nodes with a queue and swap each node's children.
- Offer root.
- Poll a node, swap its children, offer non-null children.
Each node polled once.
Queue width; no recursion, so no stack-depth risk.
class Solution { public TreeNode invertTree(TreeNode root) { if (root == null) return null; Deque<TreeNode> queue = new ArrayDeque<>(); queue.offer(root); while (!queue.isEmpty()) { TreeNode node = queue.poll(); TreeNode tmp = node.left; // swap this node's children node.left = node.right; node.right = tmp; if (node.left != null) queue.offer(node.left); if (node.right != null) queue.offer(node.right); } return root; }}in the room
How to say it in the interview
talk track
- Mention that pre-, post- or level-order all work — each node just needs one swap.
- Note the solution mutates the input in place and returns the same root.
traps
- Writing
root.left = invert(root.right); root.right = invert(root.left);— the second line reads the already-overwritten left. Save one side first.
what they ask next
Follow-ups
Symmetric Tree (LC 101)?
A tree is symmetric if its left subtree mirrors its right: compare a.left with b.right and a.right with b.left recursively.
before you submit
Edge cases to test
- Empty tree → null.
- One node → unchanged.
- A left chain becomes a right chain.
practise next
Similar problems
- #101Symmetric TreeEasyin Tree Recursion
- #100Same TreeEasyin Tree Recursion
- #104Maximum Depth of Binary TreeEasyin Tree Recursion