Binary Tree Upside Down - Video Solutions

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

Approach 1: Rebuild Using DFS + Extra Structure (O(n) time, O(n) space)

Traverse the tree with DFS and store nodes along the left spine in a stack or list. The leftmost node becomes the new root. While unwinding, reconnect nodes so that the previous parent's right child becomes the new left child and the parent itself becomes the right child. This approach is conceptually simple because you explicitly track nodes before rebuilding the structure. The downside is the extra memory needed to store nodes.

Approach 2: Recursive DFS Pointer Rewiring (O(n) time, O(h) space)

This is the classic solution using recursion from Depth-First Search. Recursively move down the left subtree until reaching the leftmost node, which becomes the new root. During the recursion unwind, rewire pointers: set root.left.left = root.right and root.left.right = root. Finally, clear the original links by setting root.left = null and root.right = null. Each node is visited once, giving O(n) time. The recursion stack uses O(h) space where h is the tree height.

Approach 3: Iterative Pointer Rotation (O(n) time, O(1) space)

The optimal approach iteratively walks down the left side of the binary tree while keeping track of the previous node and previous right child. At each step, rotate pointers: the current node's left pointer becomes the stored previous right child, and its right pointer becomes the previous node. Then shift the tracking variables and continue moving left. This effectively performs a sequence of pointer rotations similar to reversing a linked list. The algorithm processes each node exactly once and uses constant extra memory.

Recommended for interviews: Interviewers typically expect the recursive DFS solution because it demonstrates a clear understanding of pointer relationships in a tree structure. Mentioning the brute-force rebuild approach shows problem exploration, but implementing either the recursive rewiring or the iterative O(1) space method signals strong mastery of tree transformations.