Flatten Binary Tree to Linked List medium

Problem Statement

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

The "linked list" should use the same TreeNode nodes as the original tree and the order should be the same as an in-order traversal of the original tree.

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: []

Example 3

Input: root = [0] Output: [0]

Steps

1. In-order Traversal: The core idea is to perform an in-order traversal of the binary tree. In-order traversal visits nodes in the order: left subtree, root, right subtree. This ensures the flattened list maintains the correct order.

2. Linked List Construction: As we traverse the tree in-order, we connect each node to the next node in the sequence using its right child. The left child of each node is set to null.

Explanation

The recursive approach simplifies the in-order traversal and list construction. The function flatten does the following:

• Base Case: If the node is null, we return.
• Recursive Calls: We recursively flatten the left subtree and then the right subtree.
• Connecting Nodes: After flattening the left subtree, we need to connect the last node of the left subtree to the root node (if there's a left subtree). Then we connect the root node to the first node of the right subtree. This creates the linked list structure.

Code

class TreeNode {
    val: number;
    left: TreeNode | null;
    right: TreeNode | null;
    constructor(val?: number, left?: TreeNode | null, right?: TreeNode | null) {
        this.val = (val===undefined ? 0 : val)
        this.left = (left===undefined ? null : left)
        this.right = (right===undefined ? null : right)
    }
}

function flatten(root: TreeNode | null): void {
    if (!root) return;

    const flattenHelper = (node: TreeNode): TreeNode => {
        if (!node) return null;

        const leftTail = flattenHelper(node.left);
        const rightTail = flattenHelper(node.right);

        if (leftTail) {
            leftTail.right = node.right;
            node.right = node.left;
            node.left = null;
        }

        return rightTail || leftTail || node;
    }
    flattenHelper(root)
};

Complexity

• Time Complexity: O(N), where N is the number of nodes in the tree. We visit each node once during the in-order traversal.
• Space Complexity: O(H) in the worst case, where H is the height of the tree. This is due to the recursive call stack. In the best case (a completely balanced tree), H = log₂(N). In the worst case (a skewed tree), H = N. An iterative approach could reduce this to O(1).