CODEWITHSUNDEEP
binary-search-treebinary-heap
Zenil
Zenil

Reputation: 1571

Why are Binary Search Trees (BST) created using a node data structure instead of arrays?

Most examples of BSTs I have seen are of the form

Class Node {
    Node left;
    Node right;
    Key key;
    Value value;
 }

But BSTs looks like a specific form of Binary Heaps with a extra constraint , namely the left child value should be less than parent value which should be less than right node value.

Binary heaps are easily implemented using arrays. Why not create BSTs using arrays making sure that this extra rule is maintained ? What are the disadvantages of doing so ?

Upvotes: 2

Views: 480

Answers (1)

Stefan Falk
Stefan Falk

Reputation: 25397

The answer is simple: You can't just dynamically change the size of an array.

The size of an array can't just be changed afterwards. If you would use an array you'd have to enlarge it or shrink it depending on what is added or removed which would cause unnecessary overhead since you would have to copy the content from the old array to the new array whenever you do that.

Using nodes that use references or pointers allow you to just (re)assign left and right to a new element accordingly whenever you insert or set it to null (or something similar) if you remove an element which gives you a much more dynamic structure.

Upvotes: 1

Related Questions