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.

Solution:

In order to avoid traversing an element more than once we keep a ListNode that its next element indicates which node is one that we have to process.

/**
 * Definition for singly-linked list.
 * public class ListNode {
 *     int val;
 *     ListNode next;
 *     ListNode(int x) { val = x; next = null; }
 * }
 */
/**
 * Definition for binary tree
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode(int x) { val = x; }
 * }
 */
public class Solution {
    public TreeNode sortedListToBST(ListNode head) {
        int count = 0;
        ListNode temp=head;
        while(temp!=null)
        {
            count++;
            temp= temp.next;
        }
        return sortedListToBST(head, count, new ListNode(0));
    }
    
    private TreeNode sortedListToBST(ListNode head, int elements, ListNode next)
    {
        if(elements == 0)
        {
            next.next = head;
            return null;
        }
        TreeNode left = sortedListToBST(head, (elements)/2, next);
        TreeNode root = new TreeNode(next.next.val);
        next.next = next.next.next;
        TreeNode right = sortedListToBST(next.next, elements-1-elements/2, next);
        root.left = left;
        root.right = right;
        return root;
    }
}