DSA problem
Flatten Binary Tree to Linked List
Given the root of a binary tree, flatten the tree into a "linked list" in-place. The resulting list must use the same TreeNode class, where the right child pointer points to the next node and the left child pointer is always null. The order of the linked list should be the preorder traversal of the tree.
A naive solution performs a preorder traversal, stores the nodes in a list, then rewires the pointers in a second pass. That is correct but uses O(n) extra space for the list (plus O(h) for the recursion stack).
The optimal in-place solution uses a clever reverse preorder twist. True preorder visits nodes root → left → right. If we instead visit in the order right → left → root and maintain a single prev pointer that tracks the most recently processed node, then at each visit we can rewire node.right = prev and node.left = null, and then update prev = node. Because we visited the nodes in the reverse of the desired order, this rewiring builds up the preorder linked list from the tail backward, in a single post-order traversal.
The algorithm visits every node once and performs constant work, so it runs in O(n) time and uses O(h) recursion stack space — there is no auxiliary list or array, satisfying the in-place spirit of the problem.
Examples
root = [1,2,5,3,4,null,6][1,null,2,null,3,null,4,null,5,null,6]root = [][]root = [0][0]Constraints
- The number of nodes in the tree is in the range [0, 2000].
- -100 <= Node.val <= 100
- Follow-up: can you flatten the tree in-place (with O(1) extra space)?
3 hints and a full solution walkthrough with step-by-step visualizations are available in the practice editor.