Flatten Binary Tree to Linked List
The key idea
The flattened order is exactly the preorder traversal (node, then left subtree, then right subtree). To do it in
O(1) extra space, walk the tree and for each node that has a left child, find the rightmost node of that left subtree, hang the node's current right subtree off it, then move the whole left subtree over to the right side and clear left. This stitches each subtree into the chain in preorder without any recursion stack.Problem
Given the root of a binary tree, flatten the tree into a "linked list":
The "linked list" should use the same TreeNode class where the right child pointer points to the next node in the list and the left child pointer is always null.
The "linked list" should be in the same order as a preorder traversal of the binary tree.
Constraints
- The number of nodes in the tree is in the range
[0, 2000]. -100 <= Node.val <= 100
Examples
Input: root = [1,2,5,3,4,null,6]
Output: [1,null,2,null,3,null,4,null,5,null,6]
Input: root = []
Output: []
Input: root = [0]
Output: [0]
Complexity
Time: O(n) Space: O(1)
See the full solution
- ✓Full worked approach
- ✓Reference code in 5 languages
- ✓Problem-solving tips
- ✓Step-by-step animated visualization
More Tree / Recursion problems
- Balanced Binary TreeEASY
- Binary Tree CamerasHARD
- Binary Tree Inorder TraversalEASY
- Binary Tree Maximum Path SumHARD
- Binary Tree PathsEASY
- Binary Tree Postorder TraversalEASY
- Binary Tree Preorder TraversalEASY
- House Robber IIIMEDIUM
- Construct Binary Tree from Inorder and Postorder TraversalMEDIUM
- Construct Binary Tree from Preorder and Inorder TraversalMEDIUM
- Convert BST to Greater TreeMEDIUM
- Count Complete Tree NodesEASY