unsorted Array to Binary Search Tree

Question

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;
}

Are you trying to make a balanced BST? If so this approach requires that the array is sorted. If not, why not iterate through the array and add sequentially to the tree? — kingkupps
– kingkupps, Commented May 10, 2018 at 3:14
@kingkupps It doesn't have to be a sorted array if you're inserting the array elements into a bst, but an array must be sorted to perform a binary search on the array. In fact, if it's ordered, and you insert them in order, the bst will devolve to a list. A balanced array also does not require sorted arrays; the balancing handles the issue I've mentioned above. — ChiefTwoPencils
– ChiefTwoPencils, Commented May 10, 2018 at 3:39
"I have this code which works for this array but not if i changed the number to something not in the middle." Can you clarify this with an example please? — ChiefTwoPencils
– ChiefTwoPencils, Commented May 10, 2018 at 3:42
@ChiefTwoPencils Right but for this code as is to produce a balanced BST, array must be sorted. Otherwise the produced tree is not guaranteed to be balanced. What do you mean by balanced array? — kingkupps
– kingkupps, Commented May 10, 2018 at 3:54

ChiefTwoPencils · Accepted Answer · 2021-12-10 16:07:20Z

6

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.

edited Dec 10, 2021 at 16:07

answered May 10, 2018 at 18:44

ChiefTwoPencils

14k8 gold badges55 silver badges80 bronze badges

Sign up to request clarification or add additional context in comments.

9 Comments

Alexis Flanigan Over a year ago

would this be what you mean?

Alexis Flanigan Over a year ago

private Node insertNode(Node currentParent, Node newNode) { if (currentParent == null) { return newNode; } else if (newNode.value > currentParent.value) { currentParent.right = insertNode(currentParent.right, newNode); } else if (newNode.value < currentParent.value) { currentParent.left = insertNode(currentParent.left, newNode); } return currentParent; }'

ChiefTwoPencils Over a year ago

@Alexisdiaz, it looks right but is difficult to read like that. Did you give it a go?

Alexis Flanigan Over a year ago

i just need to build the second one you mention yes Ive tried to made it read like code but it wont indent for me for some reason

Alexis Flanigan Over a year ago

For the arraytoBinary what is e supposed to be ?

|

Collectives™ on Stack Overflow

unsorted Array to Binary Search Tree

1 Answer 1

9 Comments

Your Answer

Hot Network Questions

Collectives™ on Stack Overflow

1 Answer 1

9 Comments

Your Answer

Sign up or log in

Post as a guest

Related