Solution: Flatten Binary Tree to Linked List

Statement

Given the root of a binary tree, the task is to flatten the tree into a linked list using the same TreeNode class. The left child pointer of each node in the linked list should always be NULL, and the right child pointer should point to the next node in the linked list. The nodes in the linked list should be in the same order as that of the preorder traversal of the given binary tree.

Constraints:

• $-100 \leq$ Node.data $\leq 100$.
• The tree contains nodes in the range $[1, 500]$.

Solution

So far, you’ve probably brainstormed some approaches and have an idea of how to solve this problem. Let’s explore some of these approaches and figure out which one to follow based on considerations such as time complexity and any implementation constraints.

Naive approach

The naive approach to flatten a binary tree into a linked list is to perform a preorder traversal of the tree and store the visited nodes in a Queue. After the traversal, start dequeuing the nodes and set the pointers of each node such that: the right pointer of the dequeued node is set to the previously dequeued node, and the left pointer is set to NULL.

However, this naive approach requires extra memory because it uses a Queue. The space complexity would be $O(n)$. However, can the problem be solved without additional data structures?

Optimized approach using depth-first search

The solution to flattening a binary tree into a linked list involves a depth-first traversal to rearrange the tree’s nodes in place. The process begins by recursively flattening the left and right subtrees. The left subtree is attached to the current node’s right, and the original right subtree is appended to the end of this newly attached left subtree. Following this pattern for each node, the tree is transformed into a singly linked list with all nodes arranged in the same order as a pre-order tree traversal. This ensures the final structure retains a linear chain of nodes without additional space.

Specifically, we start at the root node, and for each node, find the right-most node in its left subtree. We set the right pointer of the right-most node to the current node’s right pointer. After that, we set the current node’s right pointer to the current node’s left pointer. Finally, we set the current node’s left pointer to NULL. We will repeat this process for all nodes in the binary tree.