0114.md

114. Flatten Binary Tree to Linked List

Level:

Topic:

Question

Given the root of a binary tree, flatten the tree into a "linked list". Preorder Traversal

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

Intuition

Recursive:

• Traverse to the bottom and work upward
• for each subtree
  • mark the right child
  • switch left child to the right and make left null
  • traverse down to the end of the flattened linked list, (so it's right child)
  • assign the original right child to this tail node's right

Code

Time: O(n)
Space: O(n)

Recursive

public void flatten(TreeNode root) {
    // recursively traverse down the leftmost node and put the right to the left's right
    if (root == null)
        return;

    // traverse to the bottom and reconnect the bottom-most subtree
    flatten(root.left);
    flatten(root.right);

    // make left child to the right and assign left to null
    TreeNode right = root.right;
    root.right = root.left;
    root.left = null;

    // left child is been assigned to the right, find the end of the list
    while (root.right != null)
        root = root.right;

    // and assign the original right child to its right
    root.right = right;
}