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 (with the prev-pointer as the left-child and the next-pointer as the right-child), and its values should be in the order of an inorder traversal of the original tree.

Constraints:

• The number of nodes in the tree is in the range [0, 2000].
• -100 <= Node.val <= 100

Example 1

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

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

Example 2

Input: root = []

Output: []

Steps and Explanation

The key idea is to perform a post-order traversal of the binary tree. In a post-order traversal, we visit the left subtree, then the right subtree, and finally the root. As we traverse, we'll link the rightmost node of the left subtree to the root, and the root to the leftmost node of the right subtree. This effectively flattens the tree in-place.

1. Base Case: If the root is null, there's nothing to flatten.
2. Recursive Calls: Recursively flatten the left and right subtrees.
3. Linking:
   • Find the rightmost node of the left subtree (rightmostLeft). This will be the last node in the flattened left subtree.
   • If the left subtree exists, link its rightmost node to the root: rightmostLeft.right = root.
   • Find the leftmost node of the right subtree (leftmostRight). This will be the first node in the flattened right subtree.
   • Link the root to the leftmost node of the right subtree: root.right = leftmostRight.
4. Return: To simplify the linking process, we return the rightmost node of the flattened subtree. This allows for easy chaining during the recursive calls.

Code

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

    private TreeNode helper(TreeNode root) {
        if (root == null) return null;

        TreeNode leftmostRight = helper(root.right);
        TreeNode rightmostLeft = helper(root.left);

        if (rightmostLeft != null) {
            rightmostLeft.right = root.right;
            root.right = root.left;
            root.left = null;
        }

        return leftmostRight != null ? leftmostRight : rightmostLeft != null ? rightmostLeft : root;
    }
}

Complexity

• Time Complexity: O(N), where N is the number of nodes in the tree. We visit each node once during the post-order 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 could be N, resulting in O(N) space complexity. However, in an average case, the height is much less than N. An iterative approach can reduce this to O(1) space complexity.