hardTreesPure DSA~35 min
Flatten a Binary Tree Into a Right-Skewed List
Collapse a binary tree in place into a 'linked list' that follows preorder: every node's left child becomes null and its right child points to the next preorder node.
Problem
Given the root of a binary tree, flatten it in place into a linked list following preorder traversal. Each node's left pointer must be null and its right pointer must point to the next node in preorder.
Input
A binary tree root.
Output
The same tree mutated into a right-leaning list (no return needed; mutation in place).
Constraints
- 0 <= number of nodes <= 2000
- -100 <= node value <= 100
- The flatten must be done in place.
Examples
Example 1
Input
root = [1,2,5,3,4,null,6]
Output
[1,null,2,null,3,null,4,null,5,null,6]
Preorder 1,2,3,4,5,6 becomes a right-only chain.
Example 2
Input
root = []
Output
[]
An empty tree stays empty.