Convert Sorted Array/ Linked List to BST

I once found a question about which one is better for implementation of BST, a linked list or an array. The answer is the array, because it's easier to find the middle element.

These two problems explain the reason very clearly.

Convert Sorted List to BST

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

I use the typical tree traversal way to build the BST: find the middle, take it as the root. Recursively build the left subtree and the right subtree. The only problem is, our findMiddle method should not return middle element, but the element before the middle element, because the left tree is built from head to the element before the middle. Moreover, this findMiddle method needs more attention on only one element in the list case. An alternative way could be like this.

Update 2015 - 03 - 05:
In the end, finding the middle method is not really optimal, the code is too long and tedious. I decide to implement the method based on inorder traversal. Set a static ListNode curr that track the list node that is going to be set as the root of the tree(or a subtree). Recursively construct the left subtree, proceed curr node, and construct the right tree. Left tree has size / 2, root takes 1 node, so right tree has size of size - size / 2 - 1.

public class ListNode {
ListNode curr;
    public TreeNode sortedListToBST(ListNode head) {
        if(head == null)
            return null;
        curr = head;
        int size = getSize(head);
        return getBST(size);
    }
    private TreeNode getBST(int size){
        if(size <= 0)
            return null;
        TreeNode left = getBST(size / 2);
        TreeNode root = new TreeNode(curr.val);
        root.left = left;
        curr = curr.next;
        root.right = getBST(size - 1 -size / 2);
        return root;
    }
    private int getSize(ListNode head){
        int size = 0;
        while(head != null){
            head = head.next;
            size++;
        }
        return size;
    }
}

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 BuildBST {
    public TreeNode sortedListToBST(ListNode head) {
        if (head == null)
            return null;
        if (head.next == null)
            return new TreeNode(head.val);
        ListNode preMid = findMiddle(head);
        ListNode mid = preMid.next;
        TreeNode root = new TreeNode(mid.val);
        root.right = sortedListToBST(mid.next);
        preMid.next = null;
        root.left = sortedListToBST(head);
        return root;
        
    }
    private ListNode findMiddle(ListNode head)
    {
        ListNode slow = head;
        ListNode fast = head.next;
        ListNode prev = null;
        while (fast != null && fast.next != null)
        {
            fast = fast.next.next;
            prev = slow;
            slow = slow.next;
        }
        return prev == null ? slow : prev;
    }
}

Convert Sorted Array to BST

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

public class TreeNode {
      int val;
      TreeNode left;
      TreeNode right;
      TreeNode(int x) { val = x; }
  }
 
public class Solution {
    public TreeNode sortedArrayToBST(int[] num) {
        if (num == null || num.length == 0)
            return null;
        return buildTree(0, num.length - 1, num);
    }
    private TreeNode buildTree(int start, int end, int[] num)
    {
        if (start > end)
            return null;
        int mid = (start + end) / 2;
        TreeNode root = new TreeNode(num[mid]);
        root.left = buildTree(start, mid - 1, num);
        root.right = buildTree(mid + 1, end, num);
        return root;
    }
}