BST in javascript using reference objects

Question

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

Paul · Accepted Answer · 2016-11-15 15:43:34Z

2

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.

answered Nov 15, 2016 at 15:43

Paul

142k28 gold badges285 silver badges272 bronze badges

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

Comments

bohuss · Accepted Answer · 2016-11-15 15:48:45Z

0

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

answered Nov 15, 2016 at 15:48

bohuss

3362 silver badges8 bronze badges

Collectives™ on Stack Overflow

BST in javascript using reference objects

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