Calculate Height/Depth Of Binary Tree Javascript

Question

I am just a beginner, so if the error is something too obvious, I apologize .

My two questions are:

What is this.root in our school's provided code;
How can I implement the .height method in order to measure the depth of a Tree.

The explanation: We were provided with this code in the class:

function BinarySearchTree(value) {
  this.value = value;
  this.right = null;
  this.left = null;
}

BinarySearchTree.prototype.add = function(value) {
  let newLeaf = new BinarySearchTree(value)

  if(value > this.value){
    this.right === null? this.right = newLeaf : this.right.add(value)
  } else {
    this.left === null? this.left = newLeaf : this.left.add(value)
  }
};

And we were supposed to write a method to calculate the height/depth of a binary tree. Now, while practicing, I've seen something odd. Upon creation of a new node of an empty binary tree, the first node ends up being completely empty, while it proceeds to create a new node on the left side of the first empty one. Well, not empty, but whose value is undefined. Is this a desired behavior?

let newTree = new BinarySearchTree
>undefined

newTree.add(7)
>undefined

newTree.add(3)
>undefined

newTree.add(5)
>undefined

newTree
>BinarySearchTree {value: undefined, right: null, left: BinarySearchTree}
  left: BinarySearchTree {value: 7, right: null, left: BinarySearchTree}
  right: null
  value: undefined
  [[Prototype]]: Object

Now, considering the tests are passing for .add method, obviously I may be wrong in this situation, since this is the code provided to us by the teacher in the class. This is the code I keep finding online and the reason I am not getting far with my code for .heigth method is because I am unable to implement this.root:

function Node(val){
  this.value = val;
  this.left = null;
  this.right = null;
}


function BinarySearchTree(){
  this.root = null;
}

How should I proceed with the .height method? If it helps, here are the tests:

describe('Binary Search Tree', function() {
  var binarySearchTree;

  beforeEach(function() {
    binarySearchTree = new BinarySearchTree(5);
  });

  it('should have methods named "add", "contains", "depthFirstPre", "depthFirstIn", "depthFirstPost", "breadthFirst"', function() {
    expect(binarySearchTree.add).to.be.a("function");
  });

  it('should add values at the correct location in the tree', function(){
    binarySearchTree.add(2);
    binarySearchTree.add(3);
    binarySearchTree.add(7);
    binarySearchTree.add(6);
    expect(binarySearchTree.left.right.value).to.equal(3);
    expect(binarySearchTree.right.left.value).to.equal(6);
  });

  it('height method should return correct height', function() {
    binarySearchTree.left = new BinarySearchTree(3);
    binarySearchTree.left.left = new BinarySearchTree(1);
    expect(binarySearchTree.height()).to.eql(2);

    binarySearchTree.left.left.right = new BinarySearchTree(2);
    expect(binarySearchTree.height()).to.eql(3);

    binarySearchTree.left.left.left = new BinarySearchTree(0);
    expect(binarySearchTree.height()).to.eql(3);

    binarySearchTree.right = new BinarySearchTree(8);
    expect(binarySearchTree.height()).to.eql(3);
  });
}

Again, I apologize for a long question. I was trying to write all the relevant information regarding my problem. Happy holidays!

user_5459839 · Answer

What is this.root in our school's provided code

Your school's template code does not manage what is the root of the tree, so this must be managed in a variable by the driver code. In the testing code this variable is named binarySearchTree, and it really is what would be called this.root in the second (2-class) implementation.

Now, while practicing, I've seen something odd. Upon creation of a new node of an empty binary tree, the first node ends up being completely empty [...] Is this a desired behavior?

No it is not desired behavior. The template code does not provide the concept of an empty binary tree. It expects you to create the tree with at least one value, which should be provided as argument to the constructor. It is not intended to leave out the argument when calling the constructor.

The 2-class implementation provides the idea of an empty tree. But the school's template code does not; you would just have to state binarySearchTree = null if you want an empty tree. But the downside is clear: you cannot use the methods of the class to add a value to that. The only way to get the first value in a tree is to call the constructor and assign the constructed object to your binarySearchTree variable. So adding the very first value to the tree requires a different approach than adding the other values. This is also what you see in the testing code: the first value is added as argument to the constructor -- which is always called with an argument -- while the other values are added by calling the add method. This is a pity and really shows the limitations of the template code.

How can I implement the .height method in order to measure the depth of a Tree.

The idea is that you use recursion:

If there is a left child, get the height of the left subtree through recursion. If there is none, use -1 as default, as it is an empty subtree, and empty trees have a height of -1. Do the same at the right side. Get the maximum of these two values, since only the higher subtree of the two determines what is the height of the tree. Finally add one to this result so to account for the current node.

BinarySearchTree.prototype.height = function() {
  return 1 + Math.max(
    this.left  !== null ? this.left.height()  : -1,
    this.right !== null ? this.right.height() : -1
  );
};

Again, you can only run the height method an a tree that has at least one node, because of the limitations of the school's template code.

For completeness sake, the 2-class equivalent would place the above code on the Node class, and would add a wrapper method on the BinarySearchTree class, like this:

Node.prototype.height = function() {
  return 1 + Math.max(
    this.left  !== null ? this.left.height()  : -1,
    this.right !== null ? this.right.height() : -1
  );
};

BinarySearchTree.prototype.height = function() {
  return this.root === null ? -1 : root.height();
}

Calculate Height/Depth Of Binary Tree Javascript

1 Answers