Convert Sorted List to Binary Search Tree | Leetcode

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

---

Solution: First find the length of the linked list. Then form the tree bottom up by going node by node in the linked list. Check for the end condition using the start and end indexes. Form the left child sub-tree first. Take the root node. Then form the right child sub-tree.

/**
 * Definition for singly-linked list.
 * public class ListNode {
 *     int val;
 *     ListNode next;
 *     ListNode(int x) { val = x; }
 * }
 */
/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode(int x) { val = x; }
 * }
 */
public class Solution {
    private ListNode list;
    
    public TreeNode sortedListToBST(ListNode head) {
        if (head == null) return null;
        int length = 0;
        for (ListNode tmp = head; tmp != null; tmp = tmp.next, length++);
        list = head;
        return sortedListToBST(0, length - 1);
    }
    
    private TreeNode sortedListToBST(int start, int end) {
        if (start > end) return null;
        int mid = start + (end - start) / 2;
        TreeNode left = sortedListToBST(start, mid - 1);
        TreeNode parent = new TreeNode(list.val);
        parent.left = left;
        list = list.next;
        parent.right = sortedListToBST(mid + 1, end);
        return parent;
    }
}