108/109 Convert Sorted Array/LinkedList to height balanced Binary Search Tree

108 Given an array where elements are sorted in ascending order, convert it to a height balanced BST.

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

Extension: CTCI 4.3 Sorted Array to Minimal Height Tree

Convert Array:

How to get minimal tree (height balanced)?

Match the number of nodes in the left subtree to the number of nodes in the right subtree as much as possible.

-> It will also be the height balanced tree;

-> This means we want the root to be in the middle of the array. So half is less than the root, half is greater than the root, ideally.

-> Basically solve it as pre-order traversal

private TreeNode createMinimalTree(int[] nums, int start, int end)
{
    if(nums.length == 0 || end<start)
    {
        return null;
    }

    int mid = (start + end)/2;
    TreeNode n = new TreeNode(nums[mid]);
    n.left = createMinimalTree(nums, start, mid-1);
    n.right = createMinimalTree(nums, mid+1, end);

    return n;
}

public TreeNode sortedArrayToBST(int[] nums) {
    return createMinimalTree(nums, 0, nums.length-1);
}

Time complexity: O(n)

Convert LinkedList:

Solution 1: Convert the linked list to array, and then use the above solution

Solution 2: Use fast/slow runner to find the middle point

public TreeNode sortedListToBST(ListNode head) {
    return build(head, null);
}

public TreeNode build(ListNode start, ListNode end) {
    if(start == end) {
        return null;
    }

    ListNode fast = start;
    ListNode slow = start;

    while(fast != end && fast.next != end) {
        slow = slow.next;
        fast = fast.next.next;
    }

    TreeNode node = new TreeNode(slow.val);
    node.left = build(start, slow);
    node.right = build(slow.next, end);

    return node;
}

Solution 3: In-place performance.

Insert the node following the order of linked list, no finding middle element needed.

NOTES:

Instead of top-bottom, give bottom-up a try ---> Think it as in-order traversal.
The algorithm requires knowing the length of linked list first. -> Take O(N) to traverse the linked list.
Java only supports pass by value, so we need to store the head of linked list to an array or wrapper class first, in order to traverse the linked list.

    public static int getLength(ListNode head)
    {
        if(head == null)
        {
            return 0;
        }

        int len = 0;
        ListNode p = head;
        while(p != null)
        {
            len++;
            p=p.next;
        }
        return len;
    }

    public static TreeNode sortedListToBST(ListNode[] head, int start, int end)
    {
        if(head == null || end-start <0)
        {
            return null;
        }

        int mid = (start+end)/2;

        TreeNode leftTree = sortedListToBST(head, start, mid-1);

        TreeNode parent = new TreeNode(head[0].val);
        head[0] = head[0].next;
        TreeNode rightTree = sortedListToBST(head, mid+1, end);

        parent.left = leftTree;
        parent.right = rightTree;

        return parent;      
    }

    public TreeNode sortedListToBST(ListNode head) {

        //In order the memory to move the head
        ListNode[] headHolder = {head};

        return sortedListToBST(headHolder, 0, getLength(head)-1);
    }

108/109 Convert Sorted Array/LinkedList to Binary Search Tree