A Common-Sense Guide to Data Structures and Algorithms in JavaScript, Volume 1

Chapter 15

These are the solutions to the exercises found in the section ​Exercises​.

1. The tree should look like this. Note that it’s not well balanced, as the root node only has a right subtree and no left one:

   

2. Search within a balanced binary search tree takes a maximum of about log(N) steps. So, if N is 1,000, search should take a maximum of about 10 steps.

3. The greatest value within a binary search tree will always be the bottom rightmost node. We can find it by recursively following each node’s right child until we hit the bottom:

   function max(node) {
     if (node.rightChild) {
       return max(node.rightChild);
     } else {
       return node.value; ...