Binary Tree Upside Down - Solution & Explanation

Problem Overview: You are given a binary tree where every right child is either null or a leaf with a sibling. The task is to flip the tree upside down so the leftmost node becomes the new root. During the transformation, the original parent becomes the right child and the original right sibling becomes the left child.

Approach 1: Recursive DFS Re-linking (O(n) time, O(h) space)

This method uses recursion to reach the leftmost node, which will become the new root of the flipped tree. Starting from the root, recursively process root.left until the base case (a node with no left child). While the recursion unwinds, rewire pointers: the original left child's left pointer becomes the original right child, and its right pointer becomes the original parent. After rewiring, clear the original node’s left and right references to avoid cycles. The algorithm visits each node exactly once, giving O(n) time complexity. The recursion stack uses O(h) space where h is the height of the tree. This approach fits naturally with Depth-First Search patterns and is often the clearest way to reason about pointer transformations in a Binary Tree.

Approach 2: Iterative Pointer Reversal (O(n) time, O(1) space)

The iterative version performs the same transformation but avoids recursion by tracking previous nodes. Traverse down the left spine of the tree using a loop. Maintain three references: the current node, the previous parent, and the previous right child. At each step, store the next left node, then rotate pointers so the current node’s left becomes the previous right child and its right becomes the previous parent. Update the tracking pointers and continue moving left. This effectively reverses the structure layer by layer until the traversal reaches the leftmost node, which becomes the new root. Because the algorithm only stores a few pointers, it runs in O(n) time with O(1) extra space. This technique resembles linked list reversal applied along the left spine of a Tree.

Recommended for interviews: The recursive DFS solution is usually the expected explanation because it clearly expresses the structural transformation and demonstrates comfort with recursion on trees. The iterative pointer-reversal variant shows deeper understanding of pointer manipulation and space optimization. Start with the recursive explanation to demonstrate correctness, then mention the iterative O(1) space improvement if time allows.