Problem Statement

Flatten Binary Tree to Linked List

You are given a binary tree. A binary tree is a set of nodes where each node can have a left child and a right child below it. Your job is to flatten the tree into a single straight line. After you are done, every node should have nothing on its left (left is null) and the next node hangs off the right. So it becomes a chain that only goes right, like a one-directional list. The order of the chain must match a pre-order walk, which means: visit a node first, then everything in its left subtree, then everything in its right subtree. You must do this in-place, meaning you reuse the same nodes and just rewire the pointers instead of building a brand new tree. The clever part is a Morris-style trick. Morris traversal is a way to walk a tree using no extra memory by temporarily borrowing the tree's own pointers. Here we use that idea to stitch the tree into a line using only a constant amount of extra space.

mediumTreeTreesTime: O(n) · Space: O(1)

Signals to notice

flatten tree into right-skewed listin preorderin-place

Brute force first

Preorder traversal to array, build linked list from array. It is a fair place to begin because it matches the surface of the question, yet it does not capture the deeper structure that makes the problem simpler.

The key insight

For each node, find the rightmost node of its left subtree. Set that node's right to the current node's right. Then move the left subtree to the right and null out left. The goal is not to be clever for its own sake, but to remember the one relationship that keeps the solution grounded as you move forward.

Trace it on `root = [1,2,5,3,4,null,6] (1 with left 2{3,4}, right 5{_,6})`

curr=1: left=2 exists. rightmost of left subtree = 4 (2→4). Set 4.right=curr.right(5); curr.right=curr.left(2); curr.left=null. Tree now: 1→2(left 3,right 4), 4→5→6. curr=curr.right=2
curr=2: left=3 exists. rightmost of left = 3. Set 3.right=curr.right(4); curr.right=3; curr.left=null. Spine now complete: 1→2→3→4→5→6. curr=curr.right=3
curr=3: left=null, skip rewire. curr=curr.right=4
curr=4: left=null, skip. curr=curr.right=5
curr=5: left=null, skip. curr=curr.right=6
curr=6: left=null, skip. curr=curr.right=null → loop ends
Return (in-place): 1→2→3→4→5→6, all left pointers null

What must stay true

The left subtree's rightmost node connects to the current right subtree. This preserves preorder: root → left subtree → right subtree, all linked via right pointers. If that remains true after every update, the rest of the reasoning has a stable place to stand.

Shape of the loop

curr = root
while curr:
    if curr.left:
        rightmost = curr.left
        while rightmost.right: rightmost = rightmost.right
        rightmost.right = curr.right   # attach old right subtree
        curr.right = curr.left; curr.left = None
    curr = curr.right

Pseudocode only — the full worked solution lives in the Solution tab.

Easy way to go wrong

Losing the right subtree reference — save it BEFORE overwriting the right pointer with the left subtree. Most mistakes here are not about syntax; they come from losing track of what your state, pointer, or structure is supposed to mean.

Trees Pattern