CODEWITHSUNDEEP
javascriptalgorithmbinary-search-tree
seasick
seasick

Reputation: 1225

BST in javascript using reference objects

I found this algorithm from Data structures and algorithms in javascript. For the insertion method, there are two references to the root (current and parent). My question is, why can't i change both current and parent to this.root? They both point to this.root. The code does not work properly when I do that however

'use strict';

var BST = function() {
  this.root = null;

//embed _Node inside BST so it comes with when BST is created
  this._Node = function(data, left, right) {
    this.data = data;
    this.count = 1;
    this.left = left;
    this.right = right;
  };

  this._Node.prototype.show = function() {
    return this.data;
  };

  this._Node.prototype.showCount = function() {
    return this.count;
  }
};


BST.prototype.insert = function(data) {
  //use this data for a new node
  var n = new this._Node(data, null, null);
  //if root is null, put this new node and its data into root
  if (this.root === null) {
    this.root = n;
  }
  else {
    //find a child position for this node
    var current = this.root;
    var parent;
    while (true) {
      parent = current;
      if (data < current.data) {
        current = current.left;
        if (current === null) {
          parent.left = n;
          break;
        }
      }
      else {
        current = current.right;
        if (current === null) {
          parent.right = n;
          break;
        }
      }
    }
  }
};

var nums = new BST(); 
nums.insert(23); 
nums.insert(45); 
nums.insert(16); 
nums.insert(37); 
nums.insert(3); 
nums.insert(99); 
nums.insert(22);

Upvotes: 0

Views: 39

Answers (2)

bohuss
bohuss

Reputation: 336

parent is used just to hold reference of the previous node, you create new node n and then find it's position in the tree, once current becomes null, you have found the target position for node n, you need to assign it as child (left or right) to the parent node

Upvotes: 0

Paul
Paul

Reputation: 141927

current does not refer to this.root throughout the entire algorithm.

It is initialized as this.root, but then it is quickly reassigned to either current = current.left; or current = current.right;. From that moment on current is no longer this.root. It is either this.root.left or this.root.right.

On the next iteration of the while loop it will get reassigned again, but it will never be this.root again, since it is alway being reassigned to a child node of current.

parent is similar, being this.root only on the first iteration. On each subsequent iteration it is reassigned by parent = current; and since current is no longerthis.root,parentwon't bethis.root` either.

Upvotes: 2

Related Questions