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.

A height balanced BST : a height-balanced binary tree is defined as a binary tree in which the depth of the two subtrees of every node never differ by more than 1.

Example :


Given A : 1 -> 2 -> 3
A height balanced BST  :

      2
    /   \
   1     3
public class Solution {
    public int length(ListNode a) {
        int len = 0;
        while (a != null) {
            len++;
            a = a.next;
        }
        return len;
    }

    public TreeNode helper(ListNode a, int len) {
        if (len == 0)
            return null;
        int mid = (len + 1) / 2;
        ListNode t = a;
        for (int i = 1; i < mid; i++)
            t = t.next;
        TreeNode root = new TreeNode(t.val);
        root.left = helper(a, mid - 1);
        root.right = helper(t.next, len - mid);
        return root;
    }

    public TreeNode sortedListToBST(ListNode a) {
        int len = length(a);
        return helper(a, len);
    }
}

Last updated