Flatten Binary Tree to Linked List
Flatten the tree in place into a right-leaning chain in preorder order.
Open on LeetCode ↗Intuition
For each node with a left subtree: that subtree comes next in preorder, and the old right subtree resumes after the left subtree's LAST node (its rightmost). So splice: find that rightmost node, hang the right subtree there, move the left subtree to the right, repeat — O(1) space, Morris-style.
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
Local splice per node
cur has a left child → find left subtree's rightmost node; its right takes cur's old right subtree.
Shift left to right
cur.right = cur.left; cur.left = None. Preorder order is now locally correct.
Walk down
Advance cur = cur.right. Each edge is touched a constant number of times → O(n), no stack.
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.