The tree data structure

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:

Hello and welcome to the freeCodeCamp community~!

I’ve edited your post for readability. When you enter a code block into a forum post, please precede it with a separate line of three backticks and follow it with a separate line of three backticks to make it easier to read.

You can also use the “preformatted text” tool in the editor (</>) to add backticks around text.

See this post to find the backtick on your keyboard.
Note: Backticks (`) are not single quotes (’).


Do you have a question?

If so, please edit your post to include it in the Tell us what’s happening section.

The more information you give us, the more likely we are to be able to help.