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.

Top-Down approach:
In each recursive call, we to traverse half of the list’s length to find the middle element. The run time complexity is O(N lg N).

Code:
public class Solution {
    public TreeNode sortedListToBST(ListNode head) {
        int n=0;
        ListNode pointer = head;
        while(pointer!=null)
        {
            pointer = pointer.next;
            n++;
        }
        return sortedList(head, n);
    }
    
    private TreeNode sortedList(ListNode head, int length)
    {
        if (length == 0)
            return null;
        if (length == 1)
            return new TreeNode(head.val);
        ListNode pointer = head;
        for(int i=0; i<length/2; i++)
            pointer = pointer.next;
        TreeNode sol = new TreeNode(pointer.val);
        sol.left = sortedList(head, length/2);
        sol.right = sortedList(pointer.next, (length-1)/2);
        return sol;
    }

}

Bottom-up:

We can avoid traversing the whole interval using a global variable as follows. This way the algorithm running time becomes O(n).

public class Solution {

    ListNode head;

    public TreeNode sortedListToBST(ListNode head) {

        this.head=head;

        int length = 0;

        ListNode pointer = head;

        while(pointer!=null)

        {

            pointer = pointer.next;

            length++;

        }

        return sortedListToBST(0, length-1);

    }

    

    private TreeNode sortedListToBST(int begin, int end) 

    {

        if (begin>end)

            return null;

        int middlePoint = (begin+end)/2;

        TreeNode left = sortedListToBST(begin, middlePoint-1);

        TreeNode root = new TreeNode(head.val);

        head=head.next;

        root.left = left; 

        root. right = sortedListToBST(middlePoint+1, end);

        return root;

    }

}