Flip a Tree Left to Right
Solve this ProblemYou are given the root of a binary tree. Flip it left to right: at every node the left and right children trade places, all the way down. Return the root of the flipped tree.
You can build a fresh mirrored copy, or you can reuse the existing nodes and just swap their child pointers as you visit them.
Test Case 1:
Test Case 2:
Test Case 3:
Constraints
- ◆
0 ≤ number of nodes ≤ 100 - ◆
−100 ≤ node.val ≤ 100 - ◆
The tree is given as its root node (null for an empty tree); each node has a val, a left child and a right child - ◆
Return the root of the tree after swapping the left and right children of every node (the whole tree becomes its own mirror image). The result is compared as a level-order list
Try the Dry Run
Don't just read the solution — watch it execute, one step at a time.
Approach & Solutions
Brute Force — Build a Brand-New Mirrored Copy
BruteCreate a new tree instead of changing the old one. For every node, make a fresh node with the same value; its left child is the mirrored copy of the original's RIGHT subtree, and its right child is the mirrored copy of the original's LEFT subtree. An empty subtree stays empty. Every node is visited once (O(n) time) but the copy allocates n new nodes, so it also costs O(n) extra space on top of the recursion depth.
O(n)O(n)1class Solution {
2 public TreeNode flipTree(TreeNode root) {
3 if (root == null) return null;
4 TreeNode copy = new TreeNode(root.val);
5 copy.left = flipTree(root.right);
6 copy.right = flipTree(root.left);
7 return copy;
8 }
9}Optimal — Swap the Children In Place With a Stack
OptimalReuse the existing nodes. Keep a stack of nodes still to be processed, starting with the root. Pop a node, swap its left and right child pointers, and then push whichever children exist so they get their own swap later. The order in which nodes are processed does not matter — each node is swapped exactly once — so a plain stack works. No new nodes are allocated: O(n) time, and the stack holds only a frontier of pending nodes (O(h) here, never more than the tree's width).
O(n)O(h)1class Solution {
2 public TreeNode flipTree(TreeNode root) {
3 if (root == null) return null;
4 Deque<TreeNode> stack = new ArrayDeque<>();
5 stack.push(root);
6 while (!stack.isEmpty()) {
7 TreeNode node = stack.pop();
8 TreeNode tmp = node.left;
9 node.left = node.right;
10 node.right = tmp;
11 if (node.left != null) stack.push(node.left);
12 if (node.right != null) stack.push(node.right);
13 }
14 return root;
15 }
16}