Flatten Binary Tree to linked list

114.Flatten Binary Tree to Linked List

Tree

Binary Tree

Depth-First Search

Recursion

Problem Statement:

Given the root of a binary tree, flatten it to a linked list in-place. The "linked list" should be in the same order as a preorder traversal of the binary tree using the right pointers, while setting left pointers to null.

Example:

Input:

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

→

Output:

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

The flattened tree should look like: 1->2->3->4->5->6

Algorithm:

1. Save left and right subtrees
2. Set current node's left to null
3. Recursively flatten both subtrees
4. Connect right to flattened left
5. Connect end of left to flattened right

Complexity:

Time: O(n) | Space: O(h) where h is height of tree

Java Solution:

public void flatten(TreeNode root) {
    // Base case: empty tree
    if (root == null) return;
    
    // Store left and right subtrees
    TreeNode left = root.left;
    TreeNode right = root.right;
    
    // Set left pointer to null
    root.left = null;
    
    // Recursively flatten subtrees
    flatten(left);
    flatten(right);
    
    // Connect flattened left subtree to right
    root.right = left;
    
    // Find end of left subtree and connect to right
    TreeNode curr = root;
    while (curr.right != null) curr = curr.right;
    curr.right = right;
}

Python Solution:

def flatten(self, root: Optional[TreeNode]) -> None:
    # Base case: empty tree
    if not root:
        return
    
    # Store left and right subtrees
    left = root.left
    right = root.right
    
    # Set left pointer to null
    root.left = None
    
    # Recursively flatten subtrees
    self.flatten(left)
    self.flatten(right)
    
    # Connect flattened left subtree to right
    root.right = left
    
    # Find end of left subtree and connect to right
    curr = root
    while curr.right:
        curr = curr.right
    curr.right = right

C++ Solution:

void flatten(TreeNode* root) {
    // Base case: empty tree
    if (!root) return;
    
    // Store left and right subtrees
    TreeNode* left = root->left;
    TreeNode* right = root->right;
    
    // Set left pointer to null
    root->left = nullptr;
    
    // Recursively flatten subtrees
    flatten(left);
    flatten(right);
    
    // Connect flattened left subtree to right
    root->right = left;
    
    // Find end of left subtree and connect to right
    TreeNode* curr = root;
    while (curr->right) curr = curr->right;
    curr->right = right;
}