Convert Sorted List to Binary Search Tree

Question

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

Answer 1

If you have not checked out my previous post: Convert Sorted Array to Balanced Binary Search Tree (BST), you should check it out now as this solution is built upon the previous solution.

Things get a little more complicated when you have a singly linked list instead of an array. Please note that in linked list, you no longer have random access to an element in O(1) time.

Singly-linked lists contain nodes which have a data field as well as a next field, which points to the next node in the linked list.

Naive Solution:
A naive way is to apply the previous solution directly. In each recursive call, you would have to traverse half of the list's length to find the middle element. The run time complexity is clearly O(N lg N), where N is the total number of elements in the list. This is because each level of recursive call requires a total of N/2 traversal steps in the list, and there are a total of lg N number of levels (ie, the height of the balanced tree).

Hint:
How about inserting nodes following the list's order? If we can achieve this, we no longer need to find the middle element, as we are able to traverse the list while inserting nodes to the tree.

Best Solution:
As usual, the best solution requires you to think from another perspective. In other words, we no longer create nodes in the tree using the top-down approach. We create nodes bottom-up, and assign them to its parents. The bottom-up approach enables us to access the list in its order while creating nodes.

Isn't the bottom-up approach neat? Each time you are stucked 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.

Below is the code for converting a singly linked list to a balanced BST. Please note that the algorithm requires the list's length to be passed in as the function's parameters. The list's length could be found in O(N) time by traversing the entire list's once. The recursive calls traverse the list and create tree's nodes by the list's order, which also takes O(N) time. Therefore, the overall run time complexity is still O(N).

BinaryTree* sortedListToBST(ListNode *& list, int start, int end) {
    if (start > end) return NULL;
    // same as (start+end)/2, avoids overflow
    int mid = start + (end - start) / 2;
    BinaryTree *leftChild = sortedListToBST(list, start, mid-1);
    BinaryTree *parent = new BinaryTree(list->data);
    parent->left = leftChild;
    list = list->next;
    parent->right = sortedListToBST(list, mid+1, end);
    return parent;
}

BinaryTree* sortedListToBST(ListNode *head, int n) {
    return sortedListToBST(head, 0, n-1);
}

Answer 2

public TreeNode sortedListToBST(ListNode head) {
    if (head == null) return null;
    // Transform the list to array
    ArrayList<ListNode> list = new ArrayList<ListNode>();
    ListNode node = head;
    while (node != null) {
        list.add(node);
        node = node.next;
    }

    return buildBST(list);
}

private TreeNode buildBST(List<ListNode> list) {
    int mid = (0 + list.size()) / 2;
    TreeNode node = new TreeNode(list.get(mid).val);
    if (mid > 1) {
        node.left = buildBST(list.subList(0, mid));
    } else if (mid == 1) {
        node.left = new TreeNode(list.get(0).val);
    }
    if (mid + 2 < list.size()) {
        node.right = buildBST(list.subList(mid + 1, list.size()));
    } else if (mid + 2 == list.size()) {
        node.right = new TreeNode(list.get(mid + 1).val);
    }

    return node;
}

Answer 3

 import java.util.*;
 public class Solution {
 public TreeNode sortedListToBST(ListNode head) {
    if (head == null)
        return null;
    // transform the linkedlist into an arrayList
    List<ListNode> arrList = new ArrayList<ListNode>();
    ListNode temp = head;
    while (temp != null) {
        arrList.add(temp);
        temp = temp.next;
    }
    TreeNode root = createBalancedTree(arrList, 0, arrList.size());
    return root;
}

private TreeNode createBalancedTree(List<ListNode> arrList, int begin,
        int end) {
    if (begin >= end)
        return null;
    if (end - begin == 1) {
        TreeNode newNode = new TreeNode(arrList.get(begin).val);
        return newNode;
    } else {
        int mid = (begin + end) / 2;
        TreeNode newNode = new TreeNode(arrList.get(mid).val);
        newNode.left = createBalancedTree(arrList, begin, mid);
        newNode.right = createBalancedTree(arrList, mid + 1, end);
        return newNode;
    }
}}

Answer 4

int length(ListNode* head){
int res = 0;
while (head)
{
    res++;
    head = head->next;
}
return res;
}
TreeNode* helper(ListNode* head, int start, int end){
if (start > end)
    return NULL;

/*找到中间结点*/
int mid = (start + end) / 2;
ListNode* midNode = head;
for(int i=0; i< mid; i++)
    midNode = midNode->next;

TreeNode* root = new TreeNode(midNode->val);
root->left = helper(head, start, mid-1);
root->right= helper(head, mid+1, end);

return root;
}
TreeNode *sortedListToBST(ListNode *head) {
return helper(head, 0, length(head) - 1);
}

Answer 5

In Java, to get to the O(n) solution, we need to make some hack. Java passes in Object by reference. So, changing "head = head.next" have no impact on the original Object (i.e. the original head). But, we can change the content of the Object, i.e. we can modify the content of the head to be its successor. See code below.

public TreeNode sortedListToBST(ListNode head) {
    // calculate list length
    int len = 0; ListNode cur = head;
    while (cur!=null) {
        cur = cur.next;
        len++;
    }
    // build the BST
    return listToBST(head, 0, len-1);
}

private TreeNode listToBST(ListNode head, int low, int high) {
    if (low > high) return null;
    int mid = (low + high) / 2;
    // build up tree recursively
    TreeNode left = listToBST(head, low, mid-1);
    TreeNode root = new TreeNode(head.val);
    root.left = left;
    // Java pass in Object by reference, so we can't change head but we can change its content :)
    if (head.next != null) { // "move to next"
        head.val = head.next.val;
        head.next = head.next.next;
    }
    root.right = listToBST(head, mid+1, high);
    return root;
}

Answer 6

public class Solution {
public TreeNode sortedListRangeBST(ListNode head, ListNode tail) {
    if (head==tail || head==null) return null;
    ListNode curr = getMidNode(head,tail);
    TreeNode root = new TreeNode(curr.val);
    root.left = sortedListRangeBST(head,curr);
    root.right = sortedListRangeBST(curr.next,tail);
    return root;
}
public ListNode getMidNode(ListNode head, ListNode tail) {
    if (head.next==null || head.next == tail) return head;
    ListNode slow = head;
    ListNode fast = head.next.next;
    while (fast!=null && fast!=tail) {
        slow = slow.next;
        if (fast.next==null || fast.next==tail) {
            break;
        }
        fast = fast.next.next;
    }
    return slow;
}
public TreeNode sortedListToBST(ListNode head) {
    // Start typing your Java solution below
    // DO NOT write main() function
    return sortedListRangeBST(head,null);
}
}

Answer 7

public static BiNode listToBST(Node head){

    if(head == null)
        return null;
    if( head.next == null){
            return new BiNode(head.value);

    }

    //get the mid point
    Node slow = head;
    Node fast = head;
    Node slowPrev = null;

    while(fast != null && fast.next != null){
        if(slow == head){
            slow = slow.next;
            slowPrev = head;
        }
        else{
            slowPrev = slow;
            slow = slow.next;
        }

        fast = fast.next.next;
    }

    //now slow is the new root, and get two sub lists
    BiNode root = new BiNode(slow.value);

    slowPrev.next = null;
    root.node1 = listToBST(head);
    root.node2 = listToBST(slow.next);

    return root;

}

Answer 8

TreeNode *sortedListToBST(ListNode *head) {
    // Start typing your C/C++ solution below
    // DO NOT write int main() function
    int *array;
    int size = 0;
    getArrayFromLinkList(head, array, size);

    if (size == 0)
        return NULL;

    TreeNode *root = generateBST(array, 0, size-1);

    if (array)
        delete array;
    return root;
}

TreeNode* generateBST(int *array, int low, int high) {

    if(low > high)
        return NULL;

    int mid = (low+high)/2;
    TreeNode *root = new TreeNode(array[mid]);
    TreeNode *lTree = generateBST(array, low, mid-1);
    TreeNode *rTree = generateBST(array, mid+1, high);
    root->left = lTree;
    root->right = rTree;
    return root;

}

void getArrayFromLinkList(ListNode *head, int *&array, int &size) {

    if (!head) {

        size = 0;
        array = NULL;
        return;
    }

    ListNode *p = head;
    while(p) {
        size++;
        p = p->next;
    }

    array = new int[size];
    p = head;
    for(int i=0; i<size; i++) {
        array[i] = p->val;
        p = p->next;
    }
    return;
}

Answer 9

My solution: using "divide and conquer" approach. Find the middle node of the linked list, then split around it to two lists, the left part and the right part. Set the middle node as the root, apply the algorithm recursively on the left list and the right list, set the results of them as the left child and the right child, respectively.

    public TreeNode sortedListToBST(ListNode head) {
    // Start typing your Java solution below
    // DO NOT write main() function
    //two base cases
    if(head==null)
        return null;
    if(head.next==null)
        return new TreeNode(head.val);
    ListNode fast=head.next.next;
    ListNode slow=head;
    //partition the list from the middle, use two pointers
    //the slow pointer will be the prev of the middle node
    while(fast!=null && fast.next!=null)
    {
        fast=fast.next.next;
        slow=slow.next;
    }
    //find the middle node
    ListNode parent=slow.next;
    slow.next=null;
    //partition the list into left and right
    ListNode left=head;
    ListNode right=parent.next;
    parent.next=null;
    //make the middle node as the root, then apply the function
    //to the left part and the right part recursively
    TreeNode root=new TreeNode(parent.val);                                     
    root.left=sortedListToBST(left);            
    root.right=sortedListToBST(right);
    return root;
}

Answer 10

Interesting. Building node in-order is O(n) time complexity while building node pre-order is O(nlgn) which comes from f(n) = 2f(n/2) + cn;

Way 1: build node in-order
TreeNode *sortedListToBST(ListNode *head) {
    ListNode *curr = head;
    int n = 0;
    while (curr) { n++; curr = curr->next; } 
    return sortedListToBST(head, 0, n-1);        
}
TreeNode *sortedListToBST(ListNode *&list, int start, int end)
{
    if (start > end) return NULL;
    int mid = start + (end - start) / 2;
    TreeNode *leftChild = sortedListToBST(list, start, mid-1);
    TreeNode *root = new TreeNode(list->val);
    root->left = leftChild;
    list = list->next;
    root->right = sortedListToBST(list, mid+1, end);
    return root;
}

Way 2: build node pre-order    
TreeNode *sortedListToBST(ListNode *head) {
    if (!head) return NULL;
    ListNode *slow = head;
    ListNode *fast = head->next;
    ListNode *pre_end = NULL;
    while (fast) {
        pre_end = slow;
        slow = slow->next;
        fast = (fast->next) ? fast->next->next : NULL;
    }
    if (pre_end) pre_end->next = NULL;
    TreeNode *root = new TreeNode(slow->val);

    root->left  = (pre_end == NULL) ? sortedListToBST(NULL) : sortedListToBST(head);
    root->right = sortedListToBST(slow->next);
    return root;
}

Convert Sorted List to Binary Search Tree

Follow this question

Welcome to LeetCode

Related questions