Flatten Binary Tree to Linked List
Flatten Binary Tree to Linked List: flatten the tree in place into a right-leaning chain in preorder order.
- The number of nodes in the tree is in the range [0, 2000].
- -100 <= Node.val <= 100
Intuition
To flatten binary tree to linked list, the tree must become a right-leaning chain whose order matches its preorder traversal, with every left pointer set to null — and it must happen in place.
The easy route is to record the preorder traversal into a list and then rewire, but that costs O(n) extra space. The in-place version comes from asking what happens at a single node.
Take a node with a left subtree. In preorder, that entire left subtree comes immediately after the node. And whatever used to follow the node — its right subtree — must come after the last node of that left subtree in preorder order. The last node visited in a preorder walk of a subtree is its rightmost node, reached by following right pointers as far as they go.
So the rewiring at each node is:
- Find the left subtree's rightmost node, hang the current right subtree there, then move the left subtree over to the right and null the left pointer.
Afterwards, advance to node.right and repeat. Nodes with no left child need nothing — their preorder successor is already their right child.
This is the same threading idea as a Morris traversal: the predecessor's spare pointer is used to carry the continuation, so no stack is needed and the space stays O(1).
This is the Morris-traversal idea: instead of a stack recording where to return, splice the deferred branch into the tree itself. Find the left subtree's rightmost node — the last node visited before the old right subtree would be needed — and hang the right subtree there. That makes the continuation reachable without any auxiliary memory.
Approach
Before reading on: price up what the direct approach costs here, then ask what each node needs from its children before it can answer. Aim for O(n) time and O(1) space.
Handle one node at a time
Walk a cursor down the tree. At each node the rewiring is entirely local — it needs the node, its left subtree, and its right subtree, and nothing about ancestors. That locality is what makes the O(1) space version possible.
Skip nodes with no left child
If there is no left subtree, the node's right child is already its preorder successor and nothing needs moving. Advance the cursor to node.right and continue.
Find the left subtree's rightmost node
From node.left, follow right pointers until there are none. That node is the last one visited in a preorder walk of the left subtree, so it is exactly where the original right subtree must be reattached.
Splice the right subtree onto it
Set that rightmost node's right to the current node's right subtree. The left subtree now ends by flowing into what used to follow the node — preorder order is preserved through the join.
Move the left subtree across
Set node.right = node.left and node.left = null. Nulling the left pointer is part of the specification, not tidying — a flattened tree must have no left children anywhere.
Cost of the in-place rewiring
Each edge is traversed a constant number of times — once by the cursor and once by a rightmost search — giving O(n) time and genuine O(1) space. The rightmost searches look like they add a factor, but each node is scanned by at most one of them.
Solution & live demo
Common pitfalls
Overwriting the right subtree before re-attaching it
cur.right = cur.left cur.left = None
rightmost.right = cur.right cur.right = cur.left cur.left = None
The entire right subtree is dropped — those nodes vanish from the output. It has to be spliced onto the tail of the left subtree before the pointer is reassigned.
Attaching to the left child instead of its rightmost descendant
cur.left.right = cur.right
rightmost = cur.left
while rightmost.right:
rightmost = rightmost.right
rightmost.right = cur.rightThe left child may already have its own right chain, and overwriting it discards those nodes. The old right subtree belongs after everything in the left subtree, which means at its rightmost end.
Leaving left pointers set
cur.right = cur.left cur = cur.right
cur.right = cur.left cur.left = None
The result must be a right-skewed list, so every left has to be null. A stale left pointer leaves the structure a tree that merely looks flattened along one path.
Edge cases
No left children — loop just walks the chain.
Every node splices an empty right tail — becomes the chain directly.