Flatten Binary Tree to Linked List
Medium · Trees · Linked List · Stack · Tree · Depth-First Search · Binary Tree
Problem
Given the root of a binary tree, rearrange its nodes in place into a "linked list" built from the same TreeNode objects:
- every left pointer becomes None;
- right points to the next node of the list;
- the nodes appear in preorder — a node, then its whole left subtree, then its whole right subtree.
Return nothing. The tests start at root, follow the right pointers, and compare the values they meet with the preorder list — [1,2,3,4,5,6] for the first example — and any left pointer still set fails the test.
Trees here are at most 500 levels deep, so recursion is safe. The follow-up: can you do it with O(1) extra space — no stack, no recursion, no list of nodes?
The node type and two helpers are provided:
Examples
Input: root = [1,2,5,3,4,None,6] Output: [1,None,2,None,3,None,4,None,5,None,6]
Following right pointers from 1 visits 1, 2, 3, 4, 5, 6, the preorder. Each node keeps only a right child, so in level order every value after the root is preceded by a None for its missing left child.
Input: root = [1,2,None,3] Output: [1,None,2,None,3]
A left spine becomes a right spine: each left child moves over to the right.
Constraints
- 0 <= number of nodes <= 2000
- -100 <= Node.val <= 100
- the tree is at most 500 levels deep (LeetCode allows 2,000; tightened so recursion fits in the browser)
Approaches
- Collect the preorder, then relink — time O(n), space O(n)
Follow-up
Can you flatten the tree in place with O(1) extra space: no stack, no recursion, no list of nodes? (A Morris-style walk hangs each right subtree off the rightmost node of the left subtree.)
Related problems
Start free on Cariara · Coding problems · System design studio
