LeetCode Flatten Binary Tree to Linked List: 5 methods and O(N) time O(1) Space

Overview

There are 5 different preorder based solutions to solve LeetCode Flatten Binary Tree to Linked List and the best we can achieve is O(N) time and O(1) space.

LeetCode Flatten Binary Tree to Linked List

Given a binary tree, flatten it to a linked list in-place.

For example,
Given

1
        / \
       2   5
      / \   \
     3   4   6

The flattened tree should look like:

1
    \
     2
      \
       3
        \
         4
          \
           5
            \
             6
Hints: If you notice carefully in the flattened tree, each node’s right child points to the next node of a pre-order traversal.

Analysis: 5 methods and O(N) time O(1) Space

1) We can solve this problem in a bottom up approach, that is, do a pre-order traversal, in a recursive way, we get the flatten list for each subtree, by getting the flattend list, we actually only need the head and the tail of that tree, then we append the head of the left list onto the root node, and append the head of the right list onto the tail of the left list. Just be careful when some of the list might be empty. This approach don’t need log N time to find the right most child. So the total time is linear O(N). And the space complexity would be O(h) where h is the height of the tree (i.e., the depth of the recursive calls). The following code implements this idea and is accepted by LeetCode OJ to pass this  Flatten Binary Tree to Linked List problem:

TreeNode *fattenInner(TreeNode *root) {
    if (NULL == root)
        return NULL;
    if (NULL == root->left && NULL == root->right)
        return root;

    TreeNode *lefttail  = fattenInner(root->left);
    TreeNode *righttail = fattenInner(root->right);

    TreeNode *rightHead = root->right;

    if(root->left) {
        root->right = root->left;
        lefttail->right = rightHead;
        root->left = NULL;
        if (rightHead)
            return righttail;
        else
            return lefttail;
    }
    return righttail;
}

void flatten(TreeNode *root) {
    fattenInner(root);
}

2) While the implementation in (1) does not explicitely search the right most child (tail of the flatten linked list). It could actually be done in an explicit way: For each node R, we append the left subtree of R into its right child, and append the right subtree of R onto the right most child of the left subtree of R, we basically follow a DFS order to do this and the tree will be flattened. Every time we need to find the right most subtree in a while loop but from an aggregate analysis, since for each node, the right child is set once, the final time complexity would still be O(N) and the space cost is O(h). The following code implements this idea and is accepted by LeetCode OJ to pass this  Flatten Binary Tree to Linked List problem:

void flatten(TreeNode *root) {
    if (NULL == root)
        return ;

    TreeNode *rightChild = root->right;

    root->right = root->left;
    root->left = NULL;
    TreeNode *rightMost = root;

    while (rightMost->right)
        rightMost = rightMost->right;

    rightMost->right = rightChild;
    flatten(root->right);
}

3) Seems the code gets even more compact. There is another different implementation by using a previous pointer pointing to the previous node in the preorder traversal of the tree and the code actually is easier to understand and the time and space complexity is easier to derive although it is the same as with 2). Anyways, take a look at the following code which is again accepted by LeetCode OJ to pass this Flatten Binary Tree to Linked List problem:

TreeNode *prev = NULL;
void flatten(TreeNode *root) {
    if (NULL == root)
        return;

    TreeNode *l = root->left;
    TreeNode *r = root->right;

    if (prev) {
        prev->right = root;
        prev->left = NULL;
    }

    prev = root;
    flatten(l);
    flatten(r);
}

4) Further improvement could be done by implementing the algorithm in iterative way. The easiest iterative implementation would be using an explicit stack, please see the “LeetCode Binary Tree Preorder Traversal: Iterative Using Stack” for further reference, and exact implementation could adopted. This approach still does not improve the space cost because the stack depth could still be h which is the height of the tree.

5) The final approach cost O(N) time and O(1) space: we directly simulate the process of finding the right most child of the left subtree! See the following code which is accepted:

void flatten(TreeNode *root) {
    TreeNode *rightMost = NULL;
    TreeNode *tmp = NULL;
    while (root) {
        if (root->left) {
            rightMost = root->left;
            while (rightMost->right)
                rightMost = rightMost->right;
            tmp = root->right;
            root->right = root->left;
            rightMost->right = tmp;
            root->left = NULL;
        }
        root = root->right;
    }
}

Remarks: Remember to set the left child of each node as NULL, otherwise, the OJ might report run time error

Summary

There are 5 different preorder based solutions to solve LeetCode Flatten Binary Tree to Linked List and the best we can achieve is O(N) time and O(1) space.

Written on May 23, 2013