Flatten Binary Tree to Linked List
MediumRight-child chain in preorder
Problem
Flatten a binary tree into a 'linked list' in preorder using the right pointers (left set to null).
Rewire the tree so each node's right child is the next node in preorder and left is null.
The idea
Traverse in reverse preorder — right, left, node — keeping a pointer to the previously visited node, and set each node's right to that pointer with left cleared. Working backwards means the tail is always already flattened.
The trick
- Reverse preorder: right subtree, left subtree, then the node.
- Always null the left pointer after relinking.
- A Morris-style variant does it in O(1) space.
This one walks through the worked example rather than tracing the algorithm frame by frame — a full walkthrough is still to be drawn. The code and the idea below are the real solution.
Step 1 of 2. Here's the example — [1,2,5,3,4,null,6] Values: 1, 2, 5, 3, 4, 6.
1reverse-preorder (right,left,node)2keep a prev; set node.right=prev; node.left=null; prev=nodeInput
- array
- [1, 2, 5, 3, 4, 6]
Output
- answer
- —
Check yourself
3 quick questions about this walkthrough. A wrong answer costs nothing.
Examples
Example 1
- Input:
- tree = [1,2,5,3,4,null,6]
- Output:
- [1, 2, 3, 4, 5, 6]
- Explanation:
- Becomes a right-leaning list in preorder.
Example 2
- Input:
- tree = [1]
- Output:
- [1]
- Explanation:
- Single node stays.
Example 3
- Input:
- tree = []
- Output:
- []
- Explanation:
- Empty → empty.
Practice this problem:LeetCode(opens in a new tab)Search GeeksforGeeks(opens in a new tab)
Finished the walkthrough? Add it to your streak.