Ad

Getting Middle Value Of Array To Create Balanced BST

I'm trying to find the middle element or index of an array then get the middle of each half, so on... so let say we have [0,1,2,3,4,5,6,7,8,9,10,11,12,13]

what i'm expecting 7, 3, 1, 0, 2, 5, 4, 6 ...

That way when I add elements from the new array, I end up with a balanced BST

  • start: starting index (0)
  • end: length - 1
  • nums: list of numbers to add
  • b: the tree that will insert to

Code:

 public static BST fillBST(BST b, List<Integer> nums, int start, int end) {
    int mid = (start + end) / 2;
    if (start > end)
        b.insertt(nums.get(mid));
    else {
        fillBST(b, nums, start, mid - 1);
        fillBST(b, nums, mid + 1, end);
     }
     return b;
 }

output I get using list [0,31]: 0, 0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16, 17, 18, 19, 20, 21, 22, 23, 24, 25, 26, 27, 28, 29, 30, 31

Ad

Answer

Your recursion is not properly written that's what the problem is. You should always add the mid element and then move to the left and right part if you need so.

So let's do it like that:

public static void main(String[] args) {
    List<Integer> list = Arrays.asList(new Integer[] { 0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13 });
    List<Integer> res =new ArrayList<>();
    fillBST(res, list, 0, list.size() - 1);
    System.out.println(res);
}

public static List<Integer> fillBST(List<Integer> b, List<Integer> nums, int start, int end) {
    int mid = (int)Math.round((1.0 * start + end) / 2);
    b.add(nums.get(mid));
    if (start <= mid - 1)
        fillBST(b, nums, start, mid - 1);
    if (end >= mid + 1)
        fillBST(b, nums, mid + 1, end);
    return b;
}

This prints [7, 3, 1, 0, 2, 5, 4, 6, 11, 9, 8, 10, 13, 12]

Other than the recursion condition you can see the different way I calculate mid. By calculating it int mid = (start + end) / 2; you don't round the value but truncate it. So the medium element becomes 6 in your case instead of 7.

Ad
source: stackoverflow.com
Ad