deepSWE.io

Flatten Binary Tree to Linked List

Trees

MediumLeetCode #114

Problem Statement

Given the `root` of a binary tree, flatten the tree into a "linked list":

The "linked list" should use the same `TreeNode` class where the `right` child pointer points to the next node in the list and the `left` child pointer is always `null`.
The "linked list" should be in the same order as a **pre-order traversal** of the binary tree.

Example

Algorithm Explanation

We can solve this problem using a modified pre-order traversal. The idea is to flatten the tree in place.

Algorithm Steps

Recursive Approach: We'll use a recursive function that flattens the tree and returns the tail of the flattened list.
Flatten Subtrees: For a given node, we first recursively flatten its left and right subtrees.
Rearrange Pointers: After the recursive calls, we take the flattened left subtree and make it the right child of the current node. Then, we find the tail of this new right subtree (which was the tail of the original left subtree) and attach the flattened right subtree to it.

Start

Starting flatten process. We will traverse the tree and build a linked list.

Flatten Binary Tree to Linked List Solution


class Solution:
    def flatten(self, root: Optional[TreeNode]) -> None:
        """
        Do not return anything, modify root in-place instead.
        """
        self.prev = None
        def dfs(node):
            if not node:
                return
            
            dfs(node.right)
            dfs(node.left)
            
            node.right = self.prev
            node.left = None
            self.prev = node
            
        dfs(root)