Flatten Binary Tree to Linked List - Python Solution

1. Introduction

"Flatten Binary Tree to Linked List" is an interesting problem that involves transforming a binary tree into a flattened linked list structure using the same TreeNode class. The challenge lies in reorganizing the tree nodes so that all left child pointers are null and right child pointers form a single linked list following the order of a pre-order traversal.

Problem

Given the root of a binary tree, the task is to flatten the tree into a "linked list". In this linked list, the right child pointer should point to the next node in the list, and the left child pointer should always be null. The order of nodes in the linked list should follow the pre-order traversal of the binary tree.

2. Solution Steps

1. Traverse the tree using a pre-order traversal technique.

2. As each node is visited, rearrange its pointers to form a linear linked list.

3. The right child of each node should point to the next node in the pre-order sequence, and the left child should be set to null.

4. Implement the flattening process recursively or iteratively.

5. Ensure that the final structure is a single straight line of nodes, mimicking a linked list.

3. Code Program

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

def flatten(root):
    def flattenTree(node):
        if not node:
            return None

        # Flatten the left and right subtrees
        leftTail = flattenTree(node.left)
        rightTail = flattenTree(node.right)

        # Rearrange the pointers
        if node.left:
            leftTail.right = node.right
            node.right = node.left
            node.left = None

        # Return the rightmost node after flattening
        return rightTail if rightTail else (leftTail if leftTail else node)

    flattenTree(root)

# Example Usage
root = TreeNode(1)
root.left = TreeNode(2, TreeNode(3), TreeNode(4))
root.right = TreeNode(5, None, TreeNode(6))
flatten(root)

Output:

The binary tree is flattened into a linked list in-place.

Explanation:

1. Recursive Approach: The flattenTree function flattens the binary tree recursively.

2. Subtree Flattening: It first flattens the left and right subtrees of the current node.

3. Rearranging Pointers: The right child of each node is set to the next node in the pre-order sequence, and the left child is set to null.

4. Tail Tracking: The function keeps track of the rightmost (tail) node after flattening to correctly rearrange the pointers.

5. In-Place Transformation: The tree is flattened in-place, resulting in a linked list representation following the pre-order traversal.