Tell us what’s happening:
Your code so far
/*
function Node(key) {
this.key = key;
this.left = null;
this.right = null
}
function BinarySearchTree() {
// the root node
this.root = null;
}
// helper functions
BinarySearchTree.prototype._insertNode = function(node, newNode) {
// node is the node we want to insert into
// newNode is the node we want to insert
if (newNode.key < node.key) {
// go to left
if (node.left === null) {
// no left node yet so assign
node.left = newNode;
}
else {
// move down tree and repeat
this._insertNode(node.left, newNode);
}
}
else {
// go to right
if (node.right === null) {
// no right node yet so assign
node.right = newNode;
}
else {
// move down tree and repeat
this._insertNode(node.right, newNode);
}
}
}
BinarySearchTree.prototype.insert = function(key) {
// insert new key in the tree
var newNode = new Node(key);
if (root === null) {
// no nodes yet
root = newNode;
}
else {
// find insert location through insertNode
this._insertNode(root, newNode);
}
};
// 1. Finish the implementation of the tree data structure above using the
// prototype (as opposed to the version we wrote in class). Note that we
// have helper functions that we have to deal with, and we simply make them
// part of the prototype but prepend them with _, e.g., _insertNode above.
// This is a common convention/solution. Programmers using a tree object are
// not supposed to use _ methods (or properties) directly.
// 2. Run some tests that show that your code works.
//----------------//
// Tree traversal //
//----------------//
console.log("Tree traversal");
function printNode(value) {
console.log(value);
}
// 1. Implement in-order traversal using the prototype. Test your
// implementation with the printNode() function given above.
// NOTE: in-order means all keys are visited in sorted order.
// 2. Implement pre-order traversal using the prototype. Test your
// implementation with the printNode() function given above.
// NOTE: pre-order means a node is visited prior to its descendants.
// 3. Implement post-order traversal using the prototype. Test your
// implementation with the printNode() function given above.
// NOTE: pre-order means a node is visited after its descendants.
//--------------------------------//
// Searching for values in a tree //
//--------------------------------//
console.log("Searching for values in a tree");
// 1. Implement the min method using the prototype and show that it works.
// 2. Implement the max method using the prototype and show that it works.
// 3. Implement the search method using the prototype and show that it works.
// 4. Implement the remove method using the prototype and show that it works.
// Skip.
//----------------------//
// Self-balancing trees //
//----------------------//
console.log("Self-balancing trees");
// Skip.
//---------//
// Project //
//---------//
console.log("Project");
// 1. Create the tree that is given in the book if you haven't done so yet.
// NOTE: Use the one given right before the Tree Traversal section that
// includes the 6.
// 2. We want to make a copy of this tree, but want to make sure that the copy
// we create is also nicely balanced (since we did not implement AVL). We
// can use in-order, pre-order, and post-order traversal to retrieve the
// nodes. If we want the new tree to be balanced as well, which order should
// we use if we want to insert the nodes in the new tree?
// 3. Run the traversal approach you picked in (2) to collect all the keys and
// store them in an array.
// 4. Iterate through the array and insert each element inside a new tree. make
// sure it is balanced.
*/
```js
var displayTree = tree => console.log(JSON.stringify(tree, null, 2));
function Node(value) {
this.value = value;
this.left = null;
this.right = null;
}
function BinarySearchTree() {
this.root = null;
// Only change code below this line
// Only change code above this line
}
Your browser information:
User Agent is: Mozilla/5.0 (Windows NT 10.0; Win64; x64) AppleWebKit/537.36 (KHTML, like Gecko) Chrome/86.0.4240.193 Safari/537.36.
Challenge: Find the Minimum and Maximum Height of a Binary Search Tree
Link to the challenge:
