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!