Flatten Binary Tree to Linked List - Video Solutions

Problem Overview: You receive the root of a binary tree and must transform it into a linked list in-place. The linked list should follow the same order as a preorder traversal (root → left → right). Every node’s left pointer becomes null, and the right pointer acts as the next pointer in the list.

Approach 1: Recursive Pre-order Traversal (O(n) time, O(h) space)

This approach uses a classic Depth-First Search recursion that processes nodes in preorder. Maintain a reference to the previously visited node. During traversal, set prev.right = current and prev.left = null to build the linked structure incrementally. The key insight is to traverse the right subtree after the left while rewiring pointers as you go. Time complexity is O(n) because each node is visited once. Space complexity is O(h), where h is the tree height due to the recursion stack.

Approach 2: Iterative Pre-order Traversal with Stack (O(n) time, O(n) space)

This method simulates preorder traversal using an explicit stack. Push the root node first. For each popped node, push its right child and then its left child so the left subtree is processed next. Rewire pointers by setting the current node’s right pointer to the next node on the stack and clearing left. The stack preserves preorder ordering without recursion. Time complexity remains O(n) since each node is pushed and popped once. Space complexity becomes O(n) in the worst case for skewed trees.

Both methods restructure the Binary Tree in-place without creating new nodes. The recursive approach is compact and mirrors the definition of preorder traversal. The iterative stack approach avoids recursion depth limits and provides more explicit control over traversal order.

Recommended for interviews: The recursive preorder DFS is usually the expected explanation because it clearly demonstrates pointer manipulation during traversal. Interviewers want to see that you understand preorder processing and in-place tree modification. The iterative stack version is a strong alternative when discussing recursion limits or implementing traversal without the call stack.