Flatten Binary Tree to Linked List
Flatten the tree in place into a right-leaning chain in preorder order.
Open on LeetCode ↗02
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.
03
Approach
1
Local splice per node
cur has a left child → find left subtree's rightmost node; its right takes cur's old right subtree.
2
Shift left to right
cur.right = cur.left; cur.left = None. Preorder order is now locally correct.
3
Walk down
Advance cur = cur.right. Each edge is touched a constant number of times → O(n), no stack.
04
Solution & live demo
python
▶1class Solution:
▶2 def flatten(self, root):
▶3 cur = root
▶4 while cur:
▶5 if cur.left:
▶6 rightmost = cur.left
▶7 while rightmost.right:
▶8 rightmost = rightmost.right
▶9 rightmost.right = cur.right # splice old right after left subtree
▶10 cur.right = cur.left
▶11 cur.left = None
▶12 cur = cur.right
05
Edge cases
Already right-leaning
No left children — loop just walks the chain.
Left-only tree
Every node splices an empty right tail — becomes the chain directly.
06
Complexity
Time
O(n)
Space
O(1)
Morris-style; amortized constant work per node.