Flatten Binary Tree LeetCode 114 Guide

LeetCode 114 — Flatten Binary Tree to Linked List — gives you the root of a binary tree and asks you to flatten it to a linked list in-place. The list must follow preorder traversal order: root, then all nodes from the left subtree, then all nodes from the right subtree. The catch: you must use the existing tree nodes, setting each node's right pointer to the next node in preorder sequence, and every left pointer must be set to null.

The problem looks simple on the surface — it is essentially converting a tree to a list — but the in-place constraint changes everything. You cannot build a separate list and then reassign pointers; you must rewire as you traverse. The tricky part is that modifying a node's pointers while traversing can destroy the information you need to continue. Each approach below handles this differently.

There is a well-known follow-up question: can you do it with O(1) extra space? The recursive and iterative stack solutions both use O(h) space for the call stack or explicit stack, where h is the tree height. The Morris traversal solution is the intended O(1) answer. Understanding all three gives you a complete picture of the problem.

The recursive approach processes nodes in reverse preorder — right subtree first, then left subtree, then the root — and maintains a global prev pointer that always points to the previously processed node. At each node, set node.right = prev, set node.left = null, then update prev = node. When the recursion unwinds, each node's right pointer has been set to the correct next node in preorder.

This works because reverse preorder visits nodes in the exact reverse of the desired output order. By building the list from tail to head, each node's right pointer is set to the node that should come after it — and that node has already been fully processed before we assign the pointer. There is no risk of destroying traversal state because we have already finished traversing the subtree.

The key insight is that "reverse preorder" (right → left → root) visits root last, which means by the time you process the root, both subtrees have been fully wired up. The prev pointer at that moment is the leftmost node of what was originally the left subtree — exactly where the root should point in the flattened result.

The iterative approach uses an explicit stack to simulate preorder traversal and rewire pointers on the fly. Push the root onto the stack. On each iteration, pop the top node. If that node has a right child, push it. If it has a left child, push it (left is pushed second so it is popped first). Then point the popped node's right to whatever is now at the top of the stack — the next node to be processed in preorder. Set the popped node's left to null.

This approach is intuitive if you already know how to do iterative preorder traversal. The stack maintains the correct traversal order, and at each step, you know exactly which node comes next because it is sitting at the top of the stack. Wiring node.right = stack.peek() (or checking if the stack is empty) handles all cases including leaf nodes and nodes with only one child.

The time complexity is O(n) since every node is pushed and popped exactly once. The space complexity is O(h) where h is the height of the tree — in the worst case a completely left-skewed tree — because the stack can hold at most one node per level of the right spine being built.

Morris traversal achieves O(1) extra space by using the tree structure itself as temporary storage. For each node that has a left child, find the rightmost node in the left subtree — this is called the inorder predecessor. Connect that rightmost node's right pointer to the current node's right child. Then move the entire left subtree to the right: set node.right = node.left, set node.left = null. Advance to node.right and repeat.

The effect is that the left subtree is grafted onto the right side, and its rightmost leaf now connects to what was originally the right subtree. After this operation, the current node has no left child, and its right child is the root of the combined subtree in the correct preorder order. Repeating this for every node from root downward flattens the entire tree.

Morris traversal touches each node at most twice — once when it is the current node, and once when it is being visited as the rightmost predecessor during the search. This gives O(n) time complexity with O(1) space because no stack or recursion is used. The tree's own pointers serve as the traversal mechanism.

All three approaches produce the same correct result and run in O(n) time. The difference is in space complexity and conceptual difficulty. Recursive reverse postorder is the most concise — typically 5–6 lines — and the easiest to explain once you internalize the "build from tail to head" insight. The iterative stack version is the most explicit about what preorder traversal is doing.

Morris traversal stands alone as the O(1) space solution. Its space advantage comes at the cost of being harder to read and verify. When an interviewer asks the O(1) follow-up, Morris traversal is the expected answer. Be prepared to explain why the rightmost predecessor search does not create an infinite loop — it terminates because you are looking only at the left subtree, which shrinks as the algorithm progresses.

In practice, recursive reverse postorder wins on code clarity, iterative wins on stack-overflow safety for extremely deep trees, and Morris wins on memory. For most LeetCode submissions, the recursive approach is the fastest to write correctly under time pressure.

In Python, the recursive solution uses a nonlocal prev variable initialized to None. The helper visits right, then left, then the current node: node.right = prev; node.left = None; prev = node. In Java, prev is an instance variable (TreeNode prev = null) since Java does not have nonlocal. Both are under 10 lines for the recursive core. The iterative stack solution in Python uses a deque: push root, loop while deque, pop, push right then left, set node.right = deque[0] if deque else None, set node.left = None.

The Morris traversal in Python: while node is not None, if node.left is not None, find rightmost = node.left, loop while rightmost.right is not None: rightmost = rightmost.right, then rightmost.right = node.right, node.right = node.left, node.left = None, then node = node.right. In Java the same logic with explicit null checks. This is the most interview-impressive version because O(1) space in a tree problem is unusual.

All three versions pass LeetCode 114 with identical accepted results. The recursive version is usually the first approach to reach; the Morris version is what you show after being asked the O(1) follow-up. Having both memorized as patterns — rather than derived from scratch — is the practical advantage in a timed interview setting.

Serialize and Deserialize Binary Tree (LeetCode 297) requires converting a tree to a flat string and back. While technically different from flattening to a linked list, both problems require you to traverse the tree in a specific order and preserve enough structure to reconstruct it. The preorder traversal insight from LeetCode 114 directly applies to understanding how serialization works.

Binary tree problems as a family — path sum, level order traversal, lowest common ancestor — all share the pattern of carefully managing what information is available at each node and in what order nodes are processed. LeetCode 114 is a particularly clean example because the output order (preorder) matches the traversal order that makes the solution work. Recognizing this alignment is the core of the problem.

Linked List Cycle II (LeetCode 142) uses the same O(1) space philosophy as Morris traversal: instead of extra memory, reuse the existing structure. Both problems reward candidates who understand why auxiliary space can be avoided and can articulate the mechanism. Together, these two problems cover the O(1) space constraint from both the linked list and tree angles.