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 uses the next pointer to indicate the next node in the list.
• The "linked list" should be formed by connecting all nodes from left to right.
• The "linked list" should be formed in a preorder traversal order (root, left, right).

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. Recursive Approach: We will use a recursive approach to flatten the binary tree.
2. Preorder Traversal: The core idea is to perform a preorder traversal (root, left, right) and link the nodes using the right pointer.
3. Maintaining the Tail: During the recursion, we need to keep track of the tail of the currently formed linked list. This is crucial for correctly linking the subtrees.
4. Base Case: If the node is null, we return null (the tail in this case).
5. Recursive Steps:
   • Recursively flatten the left subtree.
   • Update the tail of the left subtree to point to the root of the right subtree (linking the left and right subtrees).
   • Recursively flatten the right subtree.
   • Return the tail of the flattened tree (which will be the tail of the right subtree or the current node if there's no right subtree).

Explanation

The recursive function flatten processes the tree in a preorder manner. It first flattens the left subtree. Crucially, it then connects the tail of the flattened left subtree to the root of the right subtree. This connects the left and right subtrees sequentially. After flattening the right subtree, it returns the new tail of the entire subtree. By connecting the tail of the left subtree to the root of the right subtree, we are effectively creating the linked list structure using the right pointers.

Code

/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode() {}
 *     TreeNode(int val) { this.val = val; }
 *     TreeNode(int val, TreeNode left, TreeNode right) {
 *         this.val = val;
 *         this.left = left;
 *         this.right = right;
 *     }
 * }
 */
class Solution {
    public void flatten(TreeNode root) {
        flattenHelper(root);
    }

    private TreeNode flattenHelper(TreeNode node) {
        if (node == null) {
            return null;
        }

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

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

        if (rightTail != null) {
            return rightTail;
        } else if (leftTail != null) {
            return leftTail;
        } else {
            return node;
        }
    }
}

Complexity

• Time Complexity: O(N), where N is the number of nodes in the tree. We visit each node exactly once.
• 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. However, if we consider the iterative approach using a stack, the space complexity becomes O(1) because we don't use the recursive call stack. The iterative solution is not presented here but is another viable approach.