Implementing BST backed up by Array in Javascript

Question

I'm trying to implement bst using array, but no luck:

class BST {

  constructor() {
    this.array =[]
    this.rootSet = false;
    this.index = 0
  }

  getLeft(index) {
    return (2 * index) + 1
  }

  getRight(index) {
    return 2 * (index + 1)
  }

  getParent(index) {
    return index >>> 1
  }

  insert(value) {
    if (!this.rootSet) {
      this.rootSet = true
      this.array = [value]
      this.index++;
    } else {
      // inserts recursively.
      this.insertHelper(this.getParent(0), value);
    }
  }
  
  // helper function to insert recursively.
  insertHelper(index, value) {
    if (value < this.array[index] && this.array[this.getLeft(index)] === undefined) {
      this.array[this.getLeft(index)] = value
    } else if (value >= this.array[index] && this.array[this.getRight(index)] === undefined) {
      this.array[this.getRight(index)] = value
    } else {
      if (value < this.array[index]) {
        this.insertHelper(this.getLeft(index), value);
      } else {
        this.insertHelper(this.getRight(index), value);
      }
    }
  }
}

I tried the following:

a.insert(2)
a.insert(0)
a.insert(3)
a.insert(10)
a.insert(30)



a.array // [2, 0, 3, empty × 3, 10, empty × 7, 30]

a.array doesn't look correct. Not sure where I'm making the mistake.

this.array = [value] So you are replacing array with a new array. — epascarello
– epascarello, Commented Oct 19, 2020 at 17:15

ggorlen · Accepted Answer · 2020-10-19 17:13:48Z

Your result looks correct to me. The reason for the sparsity is that this is a typical characteristic of array-based backing structures for binary trees. If the tree isn't complete, there are wasted entries due to the empty elements representing unfilled subtrees. Since BSTs typically need balancing to retain optimal time complexity, a linked node-based approach is the typical solution, which makes rotation and balancing easier.

Typically, the array backing structure is used for binary heaps which benefit from the memory layout and speed of arrays over heap-allocated nodes and pointers; the heap operations don't permit sparsity and are easy to reason about in a linear structure using the same parent-child relationship you've used here.

Having said that, you can simplify your code considerably:

class BST {
  constructor() {
    this.array = [];
  }

  insert(value, ix=0) {
    if (this.array[ix] === undefined) {
      this.array[ix] = value;
    }
    else if (value < this.array[ix]) {
      this.insert(value, ix * 2 + 1);
    }
    else {
      this.insert(value, ix * 2 + 2);
    }
  }
}

/*
    2
   / \
  0   3
       \
        10
         \
          30
*/
const bst = new BST();
[2, 0, 3, 10, 30].forEach(e => bst.insert(e));
console.log(bst.array);

Antoine Lefebvre · Accepted Answer · 2020-10-19 16:53:53Z

1

I haven't checked the code but the result looks correct to me. The first item in the array is the root. Then the next two are the rank 1 nodes then the next 4 are the rank 2 nodes. then the next 8 are the rank 4 nodes Your result should be

answered Oct 19, 2020 at 16:53

Antoine Lefebvre

3763 silver badges10 bronze badges

Collectives™ on Stack Overflow

Implementing BST backed up by Array in Javascript

2 Answers 2

Comments

Comments

Your Answer

Hot Network Questions

Collectives™ on Stack Overflow

2 Answers 2

Comments

Comments

Your Answer

Sign up or log in

Post as a guest

Related