LeetCode Convert Sorted List to Binary Search Tree: Bottom Up Linear Time Approach

Overview

LeetCode Convert Sorted List to Binary Search Tree could be solved by an elegant bottom up BST construction algorithm in linear time and other alternatives too.

LeetCode Convert Sorted List to Binary Search Tree

Given a singly linked list where elements are sorted in ascending order, convert it to a height balanced BST.

Analysis: Bottom Up Linear Time Approach and Other Alternatives

This one is a bit more complicated than the previous array version.

1) Same way as for the array version: traverse the list and copy all the data into an array, then adopt the same method as in “Convert Sorted Array to Binary Search Tree“, this cost O(N) time and O(N) additional space

2) ** Naive Way:** although we cannot get the root node in constant time, but we still know where the root is when given the sorted list (in the middle of the list), we need to first know the length of the list say N and we just scan down the list by N/2 positions to get that root data, and adopt the same recursive call on the left sorted list and the right sorted list. And since each level of recursive call requires a total of N/2 traversal steps in the list, and there are a total of log N number of levels of the balanced BST, the total time complexity is O(N log N). The following code implemented this idea and is accepted by LeetCode OJ to pass this Convert Sorted List to Binary Search Tree problem:

class Solution {
    public:
        TreeNode *sortedListToBST(ListNode *head) {
            if (NULL == head)
                return NULL;
            if (NULL == head->next) {
                TreeNode *t = new TreeNode(head->val);
                return t;
            }

            ListNode s(0);
            s.next = head;
            ListNode *prev = &s;
            ListNode *slow = head;
            ListNode *fast = head;

            while (fast && fast->next) {
                prev = prev->next;
                slow = slow->next;
                fast = fast->next->next;
            }

            prev->next = NULL;
            TreeNode *r = new TreeNode(slow->val);
            r->left  = sortedListToBST(head);
            r->right = sortedListToBST(slow->next);
            return r;
        }
};

And note I adopt the slow/fast two pointer technique to get the middle linked list node rather than calculating the length of the linked list, the disadvantage of this method is the input linked list is modified and broken. You can try the alternative by getting the length of the list first. The following one is just my version:

TreeNode *sortedListToBSTInner(ListNode *head, int len) {
    if (len <= 0) return NULL;
    if (1 == len) {
        TreeNode *r = new TreeNode(head->val);
        return r;
    }

    int mid = len / 2;
    ListNode *pMid = head;
    while (mid--) {
        pMid = pMid->next;
    }

    TreeNode *r = new TreeNode(pMid->val);
    r->left = sortedListToBSTInner(head, len / 2);
    r->right = sortedListToBSTInner(pMid->next, len - len / 2 - 1);
    return r;
}

TreeNode *sortedListToBST(ListNode *head) {
    int len = 0;
    ListNode *p = head;
    while (p) {
        ++len;
        p = p->next;
    }
    return sortedListToBST(head, len);
}

3) Bottom up approach needs only O(N) time: 

**The bottom up approach try to build the left subtree first and then the root and then the right subtree, so different from the top down naive way of the previous one, the advantage of this approach is that we avoid to search the mid (the parent node) first as needed in the top down approach but we could just linear scan the linked list from the head to the tail. The following code is accepted by the LeetCode OJ to pass this Convert Sorted List to Binary Search Tree problem:

class Solution {
    public:
        ListNode *curr;
        TreeNode *sortedListLinear(int l, int r) {
            if (l > r)
                return NULL;
            int m = l + (r - l) / 2;
            TreeNode *leftChild = sortedListLinear(l, m - 1);
            TreeNode *root = new TreeNode(curr->val);
            root->left = leftChild;
            curr = curr->next;
            root->right = sortedListLinear(m + 1, r);
        }
        TreeNode *sortedListToBST(ListNode *head) {
            int len = 0;
            ListNode *p = head;
            while (p) {
                ++len;
                p = p->next;
            }
            curr = head;
            return sortedListLinear(0, len - 1);
        }

};

A very inspiring lesson to learn about the bottom up approach: Each time you are stuck with the top-down approach, give bottom-up a try. Although bottom-up approach is not the most natural way we think, it is extremely helpful in some cases. However, you should prefer top-down instead of bottom-up in general, since the latter is more difficult to verify in correctness.

Reference: Convert Sorted List to Balanced Binary Search Tree (BST)

Summary

LeetCode Convert Sorted List to Binary Search Tree could be solved by an elegant bottom up BST construction algorithm in linear time and other alternatives too.

Written on April 17, 2013