Flatten Binary Tree to Linked List medium

Problem Statement

Given the root of a binary tree, flatten the tree into a "linked list" in-place.

The "linked list" should use the same TreeNode nodes as the original tree and the right pointer of every node should point to the next node in the list and the left pointer of every node should be NULL.

Example 1

Input: root = [1,2,5,3,4,null,6] Output: [1,null,2,null,3,null,4,null,5,null,6]

Example 2

Input: root = [] Output: []

Steps

1. Recursive Approach: We will use a recursive post-order traversal to flatten the tree. The core idea is to process the left and right subtrees recursively, and then connect them to the current node.

2. Post-order Traversal: We flatten the right subtree first, then the left subtree, and finally connect them to the current node.

3. Connecting Nodes: After flattening the left and right subtrees, we need to connect the end of the flattened left subtree to the beginning of the flattened right subtree. This creates a continuous linked list structure.

4. Handle Null Nodes: We need to gracefully handle the cases where either the left or right subtree is null.

5. In-place Modification: The solution should modify the original tree directly without creating a new tree.

Explanation

The recursive function flatten follows these steps:

1. Base Case: If the current node is None, it does nothing.

2. Recursive Calls: It recursively flattens the left subtree and the right subtree.

3. Connecting Left Subtree: If the left subtree exists, it finds the tail of the flattened left subtree and makes it point to the original right subtree. It then updates the current node's right child to be the flattened left subtree.

4. Setting Left Child to None: It sets the left child of the current node to None to ensure we have a linked list structure.

The post-order traversal ensures that the subtrees are processed before the parent node, and the connections are made correctly to form the linked list.

Code

class TreeNode:
    def __init__(self, val=0, left=None, right=None):
        self.val = val
        self.left = left
        self.right = right

class Solution:
    def flatten(self, root: TreeNode) -> None:
        """
        Do not return anything, modify root in-place instead.
        """
        def flatten_recursive(node):
            if not node:
                return None, None # return None, None if node is None.

            left_tail, left_end = flatten_recursive(node.left)
            right_tail, right_end = flatten_recursive(node.right)

            if left_tail:
                left_end.right = node.right
                node.right = node.left
                node.left = None

            current_tail = node
            if right_end:
                current_tail = right_tail

            return node, current_tail

        flatten_recursive(root)

Complexity

• Time Complexity: O(N), where N is the number of nodes in the tree. We visit each node exactly once during the recursive traversal.
• Space Complexity: O(H), where H is the height of the tree. This is due to the recursive call stack. In the worst case (a skewed tree), H can be equal to N, resulting in O(N) space complexity. However, for a balanced tree, H is log(N), resulting in O(log N) space complexity.