So I am sure this is super easy and I am just missing it but I need to make an unsorted array to BST. I have an array int [] data = { 50, 30, 60, 10, 80, 55, 40 }; and I need to convert it to an unbalanced BST with the first number as the root no matter what I change it to and the other numbers follow the left and right rules. I have this code which works for this array but not if i changed the number to something not in the middle.
public Node arraytoBinary(int [] array, int start, int end) {
if (start > end){
return null;
}
int mid = (start + end) / 2;
Node node = new Node(array[mid]);
node.left = arraytoBinary(array, start, mid - 1);
node.right = arraytoBinary(array, mid + 1, end);
return node;
}
I don't really understand why you try to split the array and it looks like you're making some assumptions about the values and their order. (though to be honest I haven't run your code) You cannot just take for granted the direction (left, right) you'll be going. It depends on the value of the current element and the value held by the current node.
My approach to this would be to define an insert(Node node, int value) method and let the arrayToBinary simply iterate the array and call insert. This will provide you with a clean tree with a minimal interface. Plus, it's based on the definition and insertion logic of a BST so it should be intuitive.
(pseudo for your pleasure)
Insert
Node insert(node, value)
if node is null
// Create a leaf.
// It might be the root...
return new Node(value)
// It's occupied, see which way to
// go based on its value
// right? ...
if value > node.value
node.right = insert(node.right, value)
// or left?
else if value < node.value
node.left = insert(node.left, value)
// Code is not handling dups.
return node
Conversion
Node arrayToBinary(array, root)
for e in array
root = insert(root, e)
return root
This will keep the first element as the root and will insert the rest of the array as expected.