Flatten a binary tree into a linked list, in place. The list must follow preorder, using right pointers as next, with every left pointer set to null.
DSA Animator › DSA Revision › Tree › Flatten Binary Tree to Linked List
Remember: the rightmost node of the left subtree comes right before the right subtree. Splice there, move left to right, and keep walking right. The video solves Flatten Binary Tree to Linked List (LeetCode 114, Medium) with the Preorder Rewiring pattern from the Tree topic, and you can replay every step in the interactive Flatten Binary Tree to Linked List animation.
Flatten a binary tree into a linked list, in place. The list must follow preorder, using right pointers as next, with every left pointer set to null.
For the tree 1, with children 2 and 5, where 2 has children 3 and 4, and 5 has a right child 6, the result is 1, 2, 3, 4, 5, 6. That is exactly the preorder of the tree: node, then left subtree, then right subtree.
The simple way is to store the preorder in a list, and then relink the nodes one by one. That uses O of n extra space. We can rewire the pointers directly, with O of 1 extra space.
Walk down the tree with a pointer called current. If current has a left subtree, find the rightmost node of that left subtree. That rightmost node is the last one in preorder before the right subtree, so attach the right subtree to it. Then move the left subtree to the right side, and set left to null. Move current to its right child, and repeat until current is null.
Current is 1, and its left subtree is 2, 3, 4. The rightmost node of that subtree is 4, so 5 and 6 are attached to the right of 4. The subtree 2 moves to the right of 1, and the left of 1 becomes null. Current moves to 2, whose left subtree is just 3. 3 is its own rightmost node, so 4, 5, 6 hang under 3, and 3 moves to the right of 2. Current moves through 3, 4, 5 and 6, and none of them has a left child. The tree is now the chain 1, 2, 3, 4, 5, 6.
In code, loop while current is not null. If current has a left child, walk to the rightmost node of the left subtree. Set that node right to current right, set current right to current left, and set current left to null. Then move current to current right. Each edge is walked a constant number of times, so it is O of n time and O of 1 space.
Remember: the rightmost node of the left subtree comes right before the right subtree. Splice there, move left to right, and keep walking right.