Understand
30-second explanation
Build the interview-ready mental model before comparing implementations.
Rewire the tree in place so every node's left is null and right points to the next node in **preorder**. The cleanest answer walks the tree in *reversed* preorder (right → left → node), keeping a `prev` pointer to the previously processed node; at each node you set `node.right = prev`, `node.left = null`, then `prev = node`. That's O(n) time. The standout is the O(1)-space Morris-style stitch that threads each left subtree's rightmost node to the current right child.
Interview contextWhat is testedWhere candidates slipHow to stand outExplore interview contextHide interview context
What's being tested
Whether you can manipulate tree pointers in place without losing subtrees, and whether you realize processing nodes in reverse preorder makes a single `prev` pointer sufficient — versus clumsily saving and restoring right subtrees.
Where candidates slip
Overwriting `node.right` before recursing into the original right subtree (losing it), or forgetting to set `node.left = null` so the result still has dangling left pointers.
How to stand out
Lead with the reverse-preorder + prev trick, explain why walking backwards removes the need to stash the right subtree, then offer the O(1)-space Morris stitch and state its time is still O(n).
Choose
Compare the available approaches
Use constraints and trade-offs to select the route you can defend in an interview.
Interactive decision treeInteractiveChoose the right approachFirst decision previewFlatten tree to preorder right-spineNeed O(1) extra space?NoYesExplore the full treeCollapse the tree
Learn & trace
Build each solution step by step
Move from the core idea to a visual trace, implementation, proof, and edge cases.
Approach 1 of 3
Reverse Preorder with a prev Pointer
1Hint 1Explore hintHide hint
The result is a preorder chain: node → left subtree → right subtree. If you tried normal preorder you'd overwrite node.right and lose the right subtree. What if you processed nodes in the REVERSE of preorder?
2Hint 2Explore hintHide hint
Reverse preorder is right, then left, then node. Keep a single pointer `prev` to the last node you finished. What should the current node's right point to?
3Hint 3Explore hintHide hint
At each node set node.right = prev and node.left = null, then update prev = node. Because you went backwards, prev is exactly the node that should follow this one in preorder.
A · Core idea
The obstacle in flattening is that the natural traversal — preorder — wants to overwrite node.right to attach the left subtree, but the original right subtree still needs processing. If you overwrite first, you lose it. Candidates flail here, saving the right subtree in a temp variable and splicing it back at the end of the left chain, which works but is fiddly.
The elegant fix is to run preorder backwards. Preorder is node → left → right. Its exact reverse is right → left → node. If we recurse into the right subtree first, then the left subtree, and process the current node last, then by the time we touch any node, every node that should come after it in the final list has already been processed. We track that with a single prev pointer — the most recently finished node. At the current node we simply point node.right = prev, sever node.left = null, and set prev = node. No temp variables, no splicing.
Why `prev` is always the right successor. Walk the example preorder 1,2,3,4,5,6. In reverse that's 6,5,4,3,2,1 — exactly the order this recursion finishes nodes. So when we finish 6, prev becomes 6. When we finish 5, we set 5.right = 6 (correct, since 5 precedes 6 in preorder) and prev becomes 5. When we finish 4, 4.right = 5. And so on up to the root. Each node links to the node that should follow it because we discovered them in reverse order. The prev pointer is a running 'head of the already-built suffix list', and we keep prepending the current node to it.
Why nulling `left` is non-negotiable. The output contract says every left must be null. After we redirect right, the old left pointer is stale — it still points into the subtree we already relocated onto the right spine. Leaving it creates a tangled structure that looks right when you follow .right but fails strict validation and breaks any consumer that inspects left. Setting node.left = null is one line and it's the line people forget.
Why O(n) is optimal and what's left to squeeze. Every node must be touched to be relinked, so linear time is the floor. The only cost we can attack is the O(h) recursion stack — which the Morris-style approach eliminates by threading pointers instead of recursing.
B · Visual dry run
Interactive dry run
Select a frame to connect the decision with its visual state.
root = [1,2,5,3,4,null,6]Interactive diagram
Before flattening: [1,2,5,3,4,null,6]
finish 6Preorder is 1,2,3,4,5,6 — the order the flattened right-spine must follow.
1→2→3→4→5→6 (all left pointers null)C · Code with teaching comments
Reference implementation preview// Definition for a binary tree node. class TreeNode { int val; TreeNode left; TreeNode right;Explore the full codeHide the full code
D · Why it works and complexityO(n) timeO(h) spaceOpen the invariant and proofExplore the proofHide the proof
Reversing the traversal turns a 'save-and-restore the right subtree' headache into a one-pointer prepend. Whenever an in-place linked-structure rewrite feels like it needs temp storage, ask: 'what if I built the list from the tail forward?' Processing in reverse order is the recurring trick (it's also how you reverse a linked list with a prev pointer).
ComplexityO(n) time, O(h) space — Each node is visited exactly once and does O(1) pointer work → O(n) time. The recursion depth equals the tree height h → O(h) call-stack space (O(log n) balanced, O(n) degenerate).
E · Edge cases and pitfalls4Recursing left before right — that's forward preorder and overwrites the right subtree before you process it.Explore edge casesHide edge cases
Pitfalls
- Recursing left before right — that's forward preorder and overwrites the right subtree before you process it.
- Forgetting root.left = null, leaving dangling left pointers.
- Declaring prev as a local variable that resets each call instead of shared state across the recursion.
- Returning a value when the signature is void — flatten mutates in place.
Approach 2 of 3
Iterative Preorder with an Explicit Stack
1Hint 1Explore hintHide hint
Recursion is a stack the runtime manages. Make it explicit: push the root, then pop a node and process it in preorder. What two children do you push, and in what order?
2Hint 2Explore hintHide hint
Push right child then left child, so the left pops first (preorder visits left before right). Keep a `prev` pointer to the last node you popped.
3Hint 3Explore hintHide hint
On each pop, link prev.right = curr and prev.left = null, then push curr's right then left. The stack remembers the right subtrees you haven't strung up yet.
A · Core idea
If you'd rather walk forward in preorder, an explicit stack gives you the order directly. We push the root, then repeatedly pop the top node, which — because of how we push children — is always the next node in preorder.
The push order is reversed on purpose. Preorder visits node, then left, then right. A stack is LIFO, so to pop left before right we must push right before left. After popping curr, we push curr.right first and curr.left second; the left child sits on top and comes out next, exactly as preorder demands. This is the same right-then-left push trick used for iterative preorder traversal in general.
Why we save the children before rewiring. Here's the subtlety: we want to set prev.right = curr, but prev's original children matter only in that we've already pushed them. For the current node, we must push curr.right and curr.left onto the stack before we let the next iteration overwrite curr.right. Concretely, we read and push the children at the top of the loop body, then do the relinking through prev. Get this ordering wrong and you'll push a right pointer that a later iteration has already clobbered.
The prev relink is the same idea as approach one, just forward. We keep a prev pointer to the previously popped node. On each pop we do prev.right = curr; prev.left = null; then advance prev = curr. Because pops come out in preorder, stringing each popped node onto the previous one's right builds the preorder chain directly. The first pop (the root) has no prev, so we guard that with a null check.
Why this is O(h) not O(1). The stack can hold an entire path of pending right subtrees. On a left-skewed tree that's O(n); on a balanced tree O(log n). It's strictly more space than the Morris approach, but many interviewers accept it as the 'iterative' answer and it's far easier to write correctly under pressure than threading.
B · Visual dry run
Interactive dry run
Select a frame to connect the decision with its visual state.
root = [1,2,5,3,4,null,6]pop 1
push 5, push 2; prev=null so no link yet; prev=1
stack=[2,5]1→2→3→4→5→6 (all left pointers null)C · Code with teaching comments
Reference implementation previewpublic void flatten(TreeNode root) { if (root == null) return; Deque<TreeNode> stack = new ArrayDeque<>(); stack.push(root); TreeNode prev = null;Explore the full codeHide the full code
D · Why it works and complexityO(n) timeO(h) spaceOpen the invariant and proofExplore the proofHide the proof
Iterative preorder = push right, push left, visit on pop. Layering a prev relink on top of that standard traversal converts 'visit' into 'append to the right-spine'. Recognizing that flatten is just 'preorder traversal where visiting means relinking' lets you reuse a traversal template you already know.
ComplexityO(n) time, O(h) space — Each node is pushed and popped exactly once with O(1) work → O(n) time. The stack holds at most one root-to-leaf path of unprocessed right children → O(h) space.
E · Edge cases and pitfalls6root = [] — Null root returns immediately — nothing pushed, no work.Explore edge casesHide edge cases
Edge cases handled
root = []Null root returns immediately — nothing pushed, no work.root = [1,2]Pop 1 (push 2), pop 2; result 1→2 with left nulls. Tests a left-only child relinks correctly.Left-skewed treeStack depth stays small (one node at a time) but the structure is already a right-spine after flatten; space is O(h).
Pitfalls
- Pushing left before right — pops in the wrong order, producing a non-preorder chain.
- Relinking prev.right = curr before pushing curr's children — overwrites curr.right so its right subtree is lost.
- Forgetting the prev == null guard on the very first pop (the root).
Approach 3 of 3 · Optimal
Morris-Style O(1) In-Place Stitching
1Hint 1Explore hintHide hint
Can you avoid both recursion and an explicit stack? Think about where the left subtree needs to be inserted in the final chain.
2Hint 2Explore hintHide hint
For a node with a left child, the entire left subtree should slot in between the node and its current right subtree. The left subtree's RIGHTMOST node is where the right subtree must reattach.
3Hint 3Explore hintHide hint
Find the left subtree's rightmost node, point its right at the current node's right, then move the whole left subtree to the right and null the left. Advance to node.right and repeat.
A · Core idea
The follow-up asks for constant extra space, which rules out both recursion (call stack) and an explicit stack. Morris-style stitching achieves it by rewiring pointers on the fly, never storing more than a couple of local references.
The geometric insight. In the final preorder chain, a node's left subtree must appear immediately after the node and before its right subtree. So for any node curr that has a left child, we want to splice the entire left subtree into the gap between curr and curr.right. The question is where the old right subtree reattaches: it must hang off the last node of the spliced-in left subtree — and in a flattened (right-spine) left subtree, that last node is the left subtree's rightmost node, found by walking .right from curr.left until it ends.
The three-pointer surgery. For each curr with a left child: (1) find pred, the rightmost node of curr.left; (2) set pred.right = curr.right, hanging the old right subtree onto the tail of the left subtree; (3) set curr.right = curr.left and curr.left = null, moving the left subtree onto the right and clearing the left pointer. Then advance curr = curr.right and repeat. Nodes with no left child need no surgery — we just step right. When curr becomes null, the whole tree is a right-spine in preorder.
Why this yields preorder. At each node we guarantee its immediate successor is the head of its former left subtree (since we just moved left onto right), and the former right subtree is reattached after the entire left subtree's tail. That is exactly the preorder recurrence node → left → right, applied lazily one node at a time as curr marches down the evolving right-spine. Crucially we never lose the right subtree because we relink it onto pred.right before overwriting curr.right.
Why it's O(n) despite the inner 'find rightmost' loop. It looks like a nested loop, but each edge of the tree is traversed at most a constant number of times across the whole run — the predecessor-finding walks reuse the same right edges that later become part of the spine. The amortized cost is linear, identical to Morris inorder traversal. The price is that the algorithm mutates pointers mid-flight, so like all Morris techniques it's unsafe to run concurrently on a shared tree.
B · Visual dry run
Interactive dry run
Select a frame to connect the decision with its visual state.
root = [1,2,5,3,4,null,6]Interactive diagram
Choosing how to flatten
curr=1All routes hit O(n) time; they differ in space and how cleverly they avoid losing the right subtree.
1→2→3→4→5→6 (all left pointers null)C · Code with teaching comments
D · Why it works and complexityO(n) timeO(1) spaceOpen the invariant and proofExplore the proofHide the proof
The trick is recognizing WHERE the right subtree must reattach: the rightmost node of the (soon-to-be-spine) left subtree. Once you see that the left subtree's tail is the join point, the three pointer assignments write themselves. This 'find the predecessor and thread through it' move is the same engine behind Morris inorder traversal.
ComplexityO(n) time, O(1) space — Each node is visited a constant number of times and finding each rightmost predecessor traverses edges that are touched O(1) amortized times → O(n) total. No recursion and no auxiliary container → O(1) extra space.
E · Edge cases and pitfalls7root = [0] — curr=0 has no left child → loop advances to null immediately; tree unchanged, already a single-node list.Explore edge casesHide edge cases
Edge cases handled
root = [0]curr=0 has no left child → loop advances to null immediately; tree unchanged, already a single-node list.Right-skewed treeNo node has a left child, so no surgery happens — O(n) walk down the existing right-spine.Left-skewed treeEvery node triggers the stitch; the rightmost-predecessor walks are short and amortize to O(n) total.
Pitfalls
- Overwriting curr.right before reattaching the right subtree to pred.right — loses the right subtree.
- Walking pred with pred.left instead of pred.right when finding the rightmost node.
- Forgetting curr.left = null, leaving the left subtree referenced from two places.
- Reaching for this in a concurrent/read-only context — it mutates pointers during the walk.
Practice
Try the solution yourself
Edit the optimal implementation, test another input, and observe the result.
Editable code previewpublic void flatten(TreeNode root) { TreeNode curr = root; while (curr != null) { if (curr.left != null) { TreeNode pred = curr.left; // rightmost of left subtreeExplore the playgroundClose the playground
Avoid mistakes
Recognize the interview traps
Understand why common attempts fail before reviewing the corrected implementation.
1Losing the right subtree by overwriting too early
Forward preorder attaches the left subtree to node.right, but the original right subtree hasn't been processed yet. Overwriting node.right without saving it first drops an entire subtree.
Explore the code comparisonHide the code comparison
Losing the right subtree by overwriting too early
Forward preorder attaches the left subtree to node.right, but the original right subtree hasn't been processed yet. Overwriting node.right without saving it first drops an entire subtree.
Don't write this
// forward preorder, no save
flatten(root.left);
root.right = root.left; // original right subtree lost!
root.left = null;Write this instead
// reverse preorder: prev is the already-built successor
flatten(root.right);
flatten(root.left);
root.right = prev;
root.left = null;
prev = root;2Forgetting to null the left pointer
The output contract requires every left pointer to be null. Relinking right but leaving left intact produces a structure that follows correctly via .right but fails validation and confuses consumers.
Explore the code comparisonHide the code comparison
Forgetting to null the left pointer
The output contract requires every left pointer to be null. Relinking right but leaving left intact produces a structure that follows correctly via .right but fails validation and confuses consumers.
Don't write this
node.right = self.prev
self.prev = node # left pointer never cleared!Write this instead
node.right = self.prev
node.left = None
self.prev = node3Resetting prev on every recursive call
prev must persist across the entire recursion as shared state (a field or closure variable). Declaring it as a fresh local in the helper resets it each call, so links are never built.
Explore the code comparisonHide the code comparison
Resetting prev on every recursive call
prev must persist across the entire recursion as shared state (a field or closure variable). Declaring it as a fresh local in the helper resets it each call, so links are never built.
Don't write this
def visit(node):
prev = None # local: reset every call, useless
if not node: return
visit(node.right); visit(node.left)
node.right = prevWrite this instead
self.prev = None
def visit(node):
if not node: return
visit(node.right); visit(node.left)
node.right = self.prev
node.left = None
self.prev = nodeRevise
Carry the pattern into the interview
Pattern to remember
In-place rewiring to a preorder right-spine (reverse-preorder with a prev pointer, or Morris stitching)
Code pattern to memorize
reverse preorder (right, left, node):
flatten(node.right)
flatten(node.left)
node.right = prev
node.left = null
prev = nodeRules to remember
- 1The target order is preorder: node, then its (former) left subtree, then its (former) right subtree, all strung along
.right. - 2Process nodes in reverse preorder (right, left, self) so
prevalways holds the node that should come after the current one. - 3Always null out `left` after rewiring — leaving stale left pointers is the most common silent bug.
- 4Save
node.right(or use reverse order) before you overwrite it, or you lose the right subtree forever. - 5The Morris/O(1) variant links each node's left subtree's rightmost node to the node's current right child, then moves left up to right.
Use this pattern when
- Asked to convert/serialize a tree into a single chain following a traversal order
- In-place transformation where extra space should be minimized
- You can express the result as 'previous node points to current' processed backwards
- Preorder flattening, right-spine linearization, or tree-to-list questions
Choose another pattern when
- You must return a NEW structure and keep the original intact → build fresh nodes instead of rewiring
- Order required is level-order, not preorder → that's a BFS linearization
- You need a doubly linked list from a BST in sorted order → that's inorder (LC 426), not preorder
- No in-place requirement and clarity matters more → a simple preorder collect + relink is fine
Interview takeaway
Flattening is preorder traversal with pointer surgery. The mental unlock is to walk *backwards* (reverse preorder) so the node you just finished is always the correct successor — then the whole thing is three assignments and a prev pointer. Morris stitching is the same idea pushed to O(1) space.
Continue
Transfer the pattern to another problem
Use a direct variation or pattern sibling to prove the idea is reusable.
Transferable patternIn-place tree-to-list rewiring via traversal order. Recognise it whenever you must linearize a tree by mutating pointers. The reverse-traversal-with-prev trick generalizes to any order (preorder here, inorder for BST-to-DLL), and the Morris-style 'thread the predecessor' move is the O(1)-space engine shared with Morris inorder traversal.
Practice queueDirect variations and pattern siblings
Direct follow-ups
- Convert BST to Sorted Doubly Linked ListComing soonSame in-place rewiring idea but using inorder (sorted) and maintaining both prev/next pointers.
- Flatten a Multilevel Doubly Linked ListComing soonList analog — splice child lists inline; same 'find the tail and reattach' move as the Morris stitch.
- Binary Tree Preorder TraversalComing soonThe traversal order this problem flattens into; the iterative stack template is identical.
- Populating Next Right Pointers in Each NodeComing soonAnother in-place pointer-rewiring problem, but linking across levels rather than along preorder.