Flatten Binary Tree to Linked List: LeetCode 114 Walkthrough

Flatten Binary Tree to Linked List (#114) is one of those problems that looks deceptively simple until you try to solve it in-place. You are given the root of a binary tree and asked to flatten it into a "linked list" that follows the same order as a preorder traversal. The catch: you must do it in-place using only the right pointers of the existing nodes.

This is a medium-difficulty problem on LeetCode and a favorite in coding interviews at companies like Google and Meta. It tests your ability to restructure a tree without allocating extra space — a skill that comes up repeatedly in tree manipulation problems.

In this walkthrough, we will cover two clean approaches to flatten binary tree to linked list leetcode style: a recursive postorder strategy and an elegant Morris-like iterative method that runs in O(1) space.

You receive the root of a binary tree. Your goal is to flatten it into a right-skewed linked list where every node has a null left child and a right child pointing to the next node in preorder. The "linked list" reuses the original TreeNode objects — you are not creating new nodes.

For example, given the tree [1,2,5,3,4,null,6], the flattened result is 1 -> 2 -> 3 -> 4 -> 5 -> 6. Notice this is exactly the preorder traversal order: root, then left subtree, then right subtree, all threaded through the right pointers.

The function signature is void — you modify the tree in-place and return nothing. This constraint eliminates solutions that build a new list from scratch. You must rewire the existing tree nodes.

The recursive approach works by flattening the left and right subtrees first, then stitching them together. Think of it as a reverse-preorder (right, left, root) recursive strategy. You process the right subtree, then the left subtree, and finally connect the current node to the previously processed node.

Here is the high-level algorithm: recursively flatten the left subtree and the right subtree. Then take the flattened left subtree and attach it to the right pointer of the current node. Walk to the tail of that flattened left subtree and attach the original flattened right subtree to its right pointer. Finally, set the left pointer of the current node to null.

An alternative elegant approach uses a global "prev" pointer. You traverse in reverse preorder (right, left, root). At each node, set node.right to prev and node.left to null, then update prev to the current node. When the recursion unwinds, every node points to the correct next node in preorder.

The iterative approach is inspired by Morris traversal and requires no recursion and no stack. It processes the tree node by node, starting from the root and working downward. For each node that has a left child, you find the rightmost node of the left subtree and connect it to the current node's right child.

The algorithm walks through the tree using a single pointer. At each step: if the current node has a left child, find the rightmost node of the left subtree. Set that rightmost node's right pointer to the current node's right child. Move the entire left subtree to the right side by setting current.right = current.left. Set current.left = null. Then advance current to current.right.

This approach runs in O(n) time because each node is visited at most twice — once when processing it and once when finding the rightmost predecessor. The space complexity is O(1) because you only use a constant number of pointers. No recursion stack, no auxiliary data structure.

Let us trace the Morris-like iterative approach on the example tree [1,2,5,3,4,null,6]. The tree has root 1, left child 2, right child 5. Node 2 has children 3 (left) and 4 (right). Node 5 has right child 6.

Step 1: current = 1. Left child exists (node 2). Find the rightmost of node 2's subtree — that is node 4. Set 4.right = 5 (save the right subtree). Set 1.right = 2. Set 1.left = null. Now the tree is 1 -> 2 -> 3 and 2 -> 4 -> 5 -> 6.

Step 2: current = 2. Left child exists (node 3). Rightmost of node 3 is node 3 itself (no right child). Set 3.right = 4. Set 2.right = 3. Set 2.left = null. Now: 1 -> 2 -> 3 -> 4 -> 5 -> 6.

Steps 3-6: current moves through nodes 3, 4, 5, 6. None of them have left children, so we simply advance. The tree is now fully flattened: 1 -> 2 -> 3 -> 4 -> 5 -> 6, matching preorder.

Empty tree: if root is null, return immediately. There is nothing to flatten. Single node: a tree with just a root is already a valid linked list — no work needed.

All left children (left-skewed tree): the algorithm processes every node since each one has a left child. This is where the Morris-like approach shines — it systematically moves every left subtree to the right without using extra space.

All right children (right-skewed tree): the tree is already flattened in preorder. The iterative approach simply walks through without making any modifications, completing in O(n) time.

Both approaches run in O(n) time where n is the number of nodes. The recursive approach uses O(h) space on the call stack where h is the tree height (O(n) in the worst case for a skewed tree). The Morris-like iterative approach uses O(1) auxiliary space, making it the preferred solution for interviews.

This problem is a masterclass in in-place tree restructuring. Unlike problems that simply traverse a tree and collect values, LeetCode 114 forces you to rewire the tree itself. This pattern appears in other problems like Convert BST to Sorted Doubly Linked List and Binary Tree Right Side View.

The Morris-like approach introduces you to the concept of threading — temporarily modifying tree pointers to eliminate the need for a stack or recursion. This is the same idea behind Morris inorder traversal, and once you understand it, you can apply it to multiple tree problems that ask for O(1) space solutions.

If you are preparing for coding interviews, practice both the recursive and iterative versions. The recursive version demonstrates clean divide-and-conquer thinking, while the iterative version shows you can optimize space. Use YeetCode flashcards to drill the preorder flatten tree pattern until the pointer manipulations become second nature.