drawRandomBST.js

/////////////////////////////////////////////////////////////////////////////////////
// GENERATING A RANDOM BINARY SEARCH TREE of a given height (numeric data)

// Next to-do: Generate a BST of a given number of nodes ?
/////////////////////////////////////////////////////////////////////////////////////

///////////////// SET UP AS STEP-THROUGH VERSION /////////////////////
document.addEventListener("click", drawRandomBST);

// PARAMETERS FOR FUNCTION:
let minValue = 0;
let maxValue = 20;
let numLevels = 4;

// INITIALIZING VARS FOR THE FUNCTION/LOOP:
let tree = {};


function drawRandomBST () {

  // Until we have the given number of levels / tree height  ... (todo: clarify the terminology here!)
  if ( getTreeHeight(tree) < numLevels ) {
    
    let newVal = getRandomIntInclusive(minValue, maxValue);
    
    console.log("------------- newval: " + newVal + "----------------");

    // Call insertValueBST for each new value, update tree with new output:
    tree = insertValueWithCoordsBST(newVal, tree);
        
    console.log("--------------------------------------");
    
  } // end "loop"
  else { console.log("Done! Tree is now height " + numLevels); }
  
  console.log("=================================");
  console.log( JSON.stringify(tree, null, '\t' ) );

  // return tree;
  
} // end function



function insertValueWithCoordsBST (newVal, tree) {
  
  // LOCAL VARS -- FOR INNER LOOP, AND DRAWING:
  let maxNodeDistance = 2**(numLevels - 1) * (nodeSize + xMargin); // based on param for outer loop, for now
  let initialX = canvasWidth/2;
  let y = nodeSize/2 + yMargin;
  let currentNode = tree;
	
  console.log("numLevels: " + numLevels);
  console.log("nodeSize: " + nodeSize);
  console.log("xMargin: " + xMargin);
  console.log("base distance: " + (nodeSize + xMargin) );
  console.log("maxNodeDistance: " + maxNodeDistance);
  
   // For the root node only 
  if (currentNode.value == undefined) {
    
    console.log("**** **** CREATING THE ROOT NODE **** ****");
        
    // SET UP ROOT NODE:
    currentNode.value = newVal;
    currentNode.x = initialX;
    currentNode.y = y;
    currentNode.level = 0; // root node is level 0

    // DRAW IT:
    fill( colorArray[currentNode.level] );
    ellipse(currentNode.x, currentNode.y, nodeSize, nodeSize);


    console.log("newvalue: " + newVal);
    console.log("CurrentNode: " + currentNode.value + " -- " + currentNode.x + ", " + currentNode.y + " -- level: " + currentNode.level);
    console.log("level: " + currentNode.level);

    
    return tree; /// THIS IS ONLY HERE SO THAT THE ROOT IS DRAWN IN ITS OWN STEP
  }
  
  
  // not sure if this is a good condition...
  while (currentNode) {
   
    console.log("newvalue: " + newVal);
    console.log("CurrentNode: " + currentNode.value + " -- " + currentNode.x + ", " + currentNode.y + " -- level: " + currentNode.level);
    console.log("level: " + currentNode.level);
    
    
    // If LESS THAN, traverse down the left subtree
    if (newVal < currentNode.value) {
      
      console.log("Newval LESS than cur");
      
      // Insert as the left child if no child exists
      if (!currentNode.leftChild) {
        console.log("***** INSERTING NEW  VAL *****");
       currentNode.leftChild = { value: newVal };
        
        // COORDS:
            // DISTANCE BETWEEN NODES:  maxNodeDistance / 2**(currentNode.level - 1);  // level 1: maxDistance, level 2: maxDistance/2, level 3: maxDistance/4 ...
        
        let nodeDistance = maxNodeDistance / 2**(currentNode.level);
        console.log("nodeDistance: " + nodeDistance);
        
        currentNode.leftChild.x = currentNode.x - ( maxNodeDistance / 2**(currentNode.level) )/2;
        currentNode.leftChild.y = currentNode.y + nodeSize + yMargin;
        currentNode.leftChild.level = currentNode.level + 1;
        
        // DRAW IT:
        fill( colorArray[currentNode.level] );
        ellipse(currentNode.leftChild.x, currentNode.leftChild.y, nodeSize, nodeSize);

        
       return tree;
  
      // Otherwise, continue traversing down the left subtree
      } else {
       console.log("Child already exists. Next node: " + currentNode.leftChild.value);
       currentNode = currentNode.leftChild; 
        
      }
    
    // If GREATER THAN OR EQUAL TO, traverse down the right subtree
    } else if (newVal >= currentNode.value) {
      
      console.log("Newval MORE/EQUAL to cur");
      
      // Insert as the right tchild if no child exists
      if (!currentNode.rightChild) {
        console.log("***** INSERTING NEW  VAL *****");
       currentNode.rightChild = { value: newVal };
        
        // COORDS:
            // DISTANCE BETWEEN NODES:  maxNodeDistance / 2**(currentNode.level - 1);  // level 1: maxDistance, level 2: maxDistance/2, level 3: maxDistance/4 ...
        
        let nodeDistance = maxNodeDistance / 2**(currentNode.level);
        console.log("nodeDistance: " + nodeDistance);
        
        currentNode.rightChild.x = currentNode.x + ( maxNodeDistance / 2**(currentNode.level) )/2;
        currentNode.rightChild.y = currentNode.y + nodeSize + yMargin;
        currentNode.rightChild.level = currentNode.level + 1;
        
        // DRAW IT:
        fill( colorArray[currentNode.level] );
        ellipse(currentNode.rightChild.x, currentNode.rightChild.y, nodeSize, nodeSize);

        
       return tree;
     
      // Otherwise, continue traversing down the right subtree
      } else {
        console.log("Child already exists. Next node: " + currentNode.rightChild.value);
        currentNode = currentNode.rightChild; 
        
      }
    }
    
    console.log( JSON.stringify(tree, null, '\t' ) );
    
  } // end "loop"

  return tree;
  
} // end function



// Output: height of the tree (NOT COUNTING THE ROOT)
function getTreeHeight (tree) {
  
  // This feels wrong, but my first idea: track the level of each node when added to the stack
  // so : [  {1, node}, {1, node}, {2, node} ... ]
  
  let level = 0; // root will be level 0
  let currentSet = {level: 0, currentNode: tree};
  let unvisitedNodes = [];
  
  while (currentSet) {
    
    console.log("Current Node " + currentSet.currentNode.value + " -- current level: " + currentSet.level);
    console.log("--------------------------");
    console.log(unvisitedNodes);

    if (currentSet.currentNode.rightChild) {
      unvisitedNodes.push( {level: currentSet.level + 1, currentNode: currentSet.currentNode.rightChild} );
      console.log("Pushed right node " + currentSet.currentNode.rightChild.value);
      
      if (currentSet.level + 1 > level) {
        level = currentSet.level + 1;
        console.log("Increased num of levels to: " + level);
      }
    }
    
    if (currentSet.currentNode.leftChild) {
      unvisitedNodes.push( {level: currentSet.level + 1, currentNode: currentSet.currentNode.leftChild} );
      console.log("Pushed left node " + currentSet.currentNode.leftChild.value);
      
      if (currentSet.level + 1 > level) {
        level = currentSet.level + 1;
        console.log("Increased num of levels to: " + level);
      }
    }
    
    // On next iteration, current node will be the unvisited node
    // that was most recently added to the stack -- last in, first out!
    currentSet = unvisitedNodes.pop();  
    
  } // end loop
  
  console.log("HEIGHT OF TREE IS: " + level);
  return level;
  
} // end function


// via MDN:
function getRandomIntInclusive(min, max) {
  min = Math.ceil(min);
  max = Math.floor(max);
  return Math.floor(Math.random() * (max - min + 1)) + min; //The maximum is inclusive and the minimum is inclusive 
}


////////////////////////////////////////////////////////////////////////////////////////////////////////////
// SETUP FOR P5JS DRAWING:
////////////////////////////////////////////////////////////////////////////////////////////////////////////

// Setup for drawing:
const canvasWidth = 1000, canvasHeight = 900;   // canvas dimensions
const nodeSize = 50;                            // given as diameter of each node
const xMargin = 10;                         // minimum X margin between nodes
const yMargin = 25;                         // Y margin between each level

// For drawing each level a different color:
let colorArray = ["#ffffba", "#baffc9", "#bae1ff", "#ffdfba", "#ffb3ba"] ;

function setup() {
  createCanvas(canvasWidth, canvasHeight);

  // 2 frames per second, easier for testing :)
  frameRate(2);

  // DRAW THE TREEEEEE
  //generateAndDrawTree();
  
  noLoop();
}

// Loops for animation, FPS controlled by frameRate() -- default is up to 60 if supported?
function draw() {

} // end draw()

// function mousePressed() {
//   //iterations++;
//   redraw();
// }

drawTree-2018-07-16.js

/////////////////////////////////////////////////////////////////////////////////////
// SEPARATED FUNCTIONS -- V1 -- GENERATING A RANDOM BINARY SEARCH TREE AND DRAWING IT

//  1. Click-through algo function > on each iteration, insert new node and pass tree to drawTreeAsAnimationFrame
//  2. Draw whole tree on each click, clearing canvas each time
//     *** Diff between frames will show order of the algo function's traversal

// PROBLEM:
// Basically repeating the same code for getTreeHeight and drawTreeAsAnimationFrame, twice to draw each frame,
// because (I think) I need to know the height of the tree to determine the initial x distance between nodes,
// and then I need to know the level of each node in order to draw it ... so I need to track the level of each node
// as I traverse it -- both initially to find the height of the tree, and again while drawing the tree!

// PROBLEM:
// With no limit on size of tree, nodes will be drawn outside of canvas
// Idea: decrease size of nodes each time coords are about to go beyond canvas size
//       ... or always decrease size of nodes for each subsequent level?

//  ---------------------------  TABLE OF CONTENTS --------------------------
// 1. drawTreeAsAnimationFrame
// - Set up global vars for drawing params and step-through function
// 2. generateAndDrawRandomBinarySearchTree
// 3. insertValueBST
// - Helper functions:
//    - getTreeHeight
//    - getRandomIntInclusive
// - Set up p5js: setup() and draw()
/////////////////////////////////////////////////////////////////////////////////////

function drawTreeAsAnimationFrame(tree, xMargin, yMargin, nodeSize, canvasWidth, canvasHeight, colorArray) {
  
  // Clear the canvas before drawing each new frame
  clear();
  
  let numLevels = getTreeHeight(tree);
  
  let maxNodeDistance = 2**(numLevels - 1) * (nodeSize + xMargin);
  let initialX = canvasWidth/2;
  let initialY = nodeSize/2 + yMargin;
  let unvisitedNodes = [];
  let currentSet = {level: 0, currentNode: tree, x: initialX, y: initialY};
	let level = 0;
  
  console.log("~~~~~~~~~~~~~~~~~~~~~~~~~~~");
  console.log("numLevels: " + numLevels);
  console.log("maxNodeDistance: " + maxNodeDistance);
  
  while (currentSet) {
    
    console.log("CurrentNode: " + currentSet.currentNode.value + " -- " + currentSet.x + ", " + currentSet.y);
    console.log("level: " + currentSet.level);
       
    // DRAW IT:
    fill( colorArray[currentSet.level] );                // ***** TO FIX: wrap around array to avoid undefined errors
    ellipse(currentSet.x, currentSet.y, nodeSize, nodeSize);
    
    if (currentSet.currentNode.leftChild) {      
      // DETERMINE NEW COORDINATES BASED ON PARENT NODE, PUSH TO STACK
      unvisitedNodes.push(
        {
          level: currentSet.level + 1,
          currentNode: currentSet.currentNode.leftChild,
          x: currentSet.x - ( maxNodeDistance / 2**(currentSet.level) )/2,  // SUBTRACT for left child
          y: currentSet.y + nodeSize + yMargin  
        });
      console.log("Pushed left node " + currentSet.currentNode.leftChild.value);
    }

    if (currentSet.currentNode.rightChild) {
      // DETERMINE NEW COORDINATES BASED ON PARENT NODE, PUSH TO STACK
      unvisitedNodes.push(
        {
          level: currentSet.level + 1,
          currentNode: currentSet.currentNode.rightChild,
          x: currentSet.x + ( maxNodeDistance / 2**(currentSet.level) )/2,  // ADD for right child
          y: currentSet.y + nodeSize + yMargin  
        });
      console.log("Pushed right node " + currentSet.currentNode.rightChild.value);
    }
       
    // On next iteration, current node will be the unvisited node (this version is depth-first)
    currentSet = unvisitedNodes.pop();
        
  } // end while

  console.log("~~~~~~~~~~~~~~~~~~~~~~~~~~~");
  
  // console.log( JSON.stringify(tree, null, '\t' ) );
 
} // end function


////////////////////////////////////////////////////////////////////////////////////////////////////////////
//     SET UP AS STEP-THROUGH VERSION TO DRAW TREE AS A FRAME ON EACH CLICK 
////////////////////////////////////////////////////////////////////////////////////////////////////////////

document.addEventListener("click", generateAndDrawRandomBinarySearchTree);

// Setup for drawing:
const canvasWidth = 1000, canvasHeight = 900;   // canvas dimensions
const nodeSize = 50;                            // given as diameter of each node
const xMargin = 10;                         // minimum X margin between nodes
const yMargin = 25;                         // Y margin between each level

// For drawing each level a different color:
let colorArray = ["#ffffba", "#baffc9", "#bae1ff", "#ffdfba", "#ffb3ba"] ;


// PARAMETERS FOR FUNCTION:
let valueType = "number"; // or "string" ???
let minValue = 0;
let maxValue = 20;

// INITIALIZING VARS FOR THE FUNCTION/LOOP:
  let tree = {};


// *** THIS VERSION: ANY NUMBER OF NODES! 
function generateAndDrawRandomBinarySearchTree () {

  let newVal = getRandomIntInclusive(minValue, maxValue);

  console.log("===============================");

  // Call insertValueBST for each new value, update tree with new output:
  tree = insertValueBST(newVal, tree);

  // DRAW THE WHOLE TREE on each iteration:
  drawTreeAsAnimationFrame(tree, xMargin, yMargin, nodeSize, canvasWidth, canvasHeight, colorArray) 

  console.log("=================================");
  console.log( JSON.stringify(tree, null, '\t' ) );
  
} // end function


function insertValueBST (newVal, tree) {
  
  console.log(" ~~~~~ CALLED insertValueBST ~~~~~");
  
  let currentNode = tree;
	
  while (currentNode) {
   
    // console.log("value: " + newVal);
    // console.log("Node " + currentNode.value);

    // CREATE THE ROOT NODE FIRST -- RETURN SO THAT IT'S DRAWN AS ITS OWN INDIVIDUAL STEP
    if (currentNode.value == undefined) {
      currentNode.value = newVal;
      return tree;
    }
    
    // If LESS THAN, traverse down the left subtree
    if (newVal < currentNode.value) {
      
      console.log("Newval: " + newVal + " is LESS than cur val: " + currentNode.value);
      
      // Insert as the left tchild if no child exists
      if (!currentNode.leftChild) {
       currentNode.leftChild = { value: newVal };
       return tree;
  
      // Otherwise, continue traversing down the left subtree
      } else {
       console.log("Child already exists. Next node: " + currentNode.leftChild.value);
       currentNode = currentNode.leftChild; 
      }
    
    // If GREATER THAN OR EQUAL TO, traverse down the right subtree
    } else if (newVal >= currentNode.value) {
      
      console.log("Newval: " + newVal + " is MORE/EQUAL to cur val: " + currentNode.value);
      
      // Insert as the right tchild if no child exists
      if (!currentNode.rightChild) {
       currentNode.rightChild = { value: newVal };
       return tree;
     
      // Otherwise, continue traversing down the right subtree
      } else {
        console.log("Child already exists. Next node: " + currentNode.rightChild.value);
        currentNode = currentNode.rightChild; 
      }
    }
    
    console.log( JSON.stringify(tree, null, '\t' ) );
    
  } // end loop

  return tree;
  
} // end function


/////////////////////////////////////////////////////////////////////////////////////
// HELPER FUNCTIONS
/////////////////////////////////////////////////////////////////////////////////////

// Output: height of the tree (NOT COUNTING THE ROOT)
function getTreeHeight (tree) {
  
  // This feels wrong, but my first idea: track the level of each node when added to the stack
  // so : [  {1, node}, {1, node}, {2, node} ... ]
  
  let level = 0; // root will be level 0
  let currentSet = {level: 0, currentNode: tree};
  let unvisitedNodes = [];
  
  while (currentSet) {
    
    console.log("Current Node " + currentSet.currentNode.value + " -- current level: " + currentSet.level);
    console.log("--------------------------");
    console.log(unvisitedNodes);

    if (currentSet.currentNode.rightChild) {
      unvisitedNodes.push( {level: currentSet.level + 1, currentNode: currentSet.currentNode.rightChild} );
      console.log("Pushed right node " + currentSet.currentNode.rightChild.value);
      
      if (currentSet.level + 1 > level) {
        level = currentSet.level + 1;
        console.log("Increased num of levels to: " + level);
      }
    }
    
    if (currentSet.currentNode.leftChild) {
      unvisitedNodes.push( {level: currentSet.level + 1, currentNode: currentSet.currentNode.leftChild} );
      console.log("Pushed left node " + currentSet.currentNode.leftChild.value);
      
      if (currentSet.level + 1 > level) {
        level = currentSet.level + 1;
        console.log("Increased num of levels to: " + level);
      }
    }
    
    // On next iteration, current node will be the unvisited node
    // that was most recently added to the stack -- last in, first out!
    currentSet = unvisitedNodes.pop();  
    
  } // end loop
  
  console.log("HEIGHT OF TREE IS: " + level);
  return level;
  
} // end function


// via MDN:
function getRandomIntInclusive(min, max) {
  min = Math.ceil(min);
  max = Math.floor(max);
  return Math.floor(Math.random() * (max - min + 1)) + min; //The maximum is inclusive and the minimum is inclusive 
}


////////////////////////////////////////////////////////////////////////////////////////////////////////////
// SETUP FOR P5JS DRAWING:
////////////////////////////////////////////////////////////////////////////////////////////////////////////

function setup() {
  createCanvas(canvasWidth, canvasHeight);

  // 2 frames per second, easier for testing :)
  frameRate(2);

  // DRAW THE TREEEEEE
  //generateAndDrawTree();
  
  noLoop();
}

// Loops for animation, FPS controlled by frameRate() -- default is up to 60 if supported?
function draw() {

} // end draw()

// function mousePressed() {
//   //iterations++;
//   redraw();
// }

generateBinarySearchTree.js

/////////////////////////////////////////////////////////////////////////////////////
// GENERATING A BINARY SEARCH TREE -- FROM AN ARRAY, IN ORDER OF ELEMENTS

// UPDATE 2018-07-08: Fixed it! For each value, call a non-step-through version of insertValueBST (see below)
// UPDATE 2018-07-07: Realized that v1 was completely broken. Oopsies.
/////////////////////////////////////////////////////////////////////////////////////

//let testArray3 = ["a", "b", "c", "d", "e", "f", "g", "h", "i", "j", "k", "l", "m", "n", "o", "p"];
let testArray2 = ["f", "d", "b", "e", "h", "a", "g", "c"];
let testArray1 = ["d", "b", "a", "c"];

///////////////// SET UP AS STEP-THROUGH VERSION /////////////////////
document.addEventListener("click", generateBinarySearchTree);

// PARAMETER FOR FUNCTION:
let arr = testArray2;

// INITIALIZING VARS FOR THE FUNCTION/LOOP:
  let tree = {};
  let currentNode = tree;
  let i = 1;
  
// BEFORE THE LOOP STARTS, SET UP ROOT NODE:
  tree.value = arr[0];

function generateBinarySearchTree () {

  // not sure if this is a good condition...
  if (i < arr.length) {
   
    let newVal = arr[i];
    
    console.log("------------------\n i: " + i + ", val: " + newVal);

    // Call insertValueBST for each new value, update tree with new output:
    tree = insertValueBST(newVal, tree);
    
    i++;
    
    console.log("--------------------------------------");
    
  } // end "loop"

  console.log("=================================");
  console.log( JSON.stringify(tree, null, '\t' ) );

  // return tree;
  
} // end function



function insertValueBST (newVal, tree) {
  
  let currentNode = tree;
	
  // not sure if this is a good condition...
  while (currentNode) {
   
    console.log("value: " + newVal);
    console.log("Node " + currentNode.value);

    // If LESS THAN, traverse down the left subtree
    if (newVal < currentNode.value) {
      
      console.log("Newval LESS than cur");
      
      // Insert as the left tchild if no child exists
      if (!currentNode.leftChild) {
       currentNode.leftChild = { value: newVal };
       return tree;
  
      // Otherwise, continue traversing down the left subtree
      } else {
       console.log("Child already exists. Next node: " + currentNode.leftChild.value);
       currentNode = currentNode.leftChild; 
      }
    
    // If GREATER THAN OR EQUAL TO, traverse down the right subtree
    } else if (newVal >= currentNode.value) {
      
      console.log("Newval MORE/EQUAL to cur");
      
      // Insert as the right tchild if no child exists
      if (!currentNode.rightChild) {
       currentNode.rightChild = { value: newVal };
       return tree;
     
      // Otherwise, continue traversing down the right subtree
      } else {
        console.log("Child already exists. Next node: " + currentNode.rightChild.value);
        currentNode = currentNode.rightChild; 
      }
    }
    
    console.log( JSON.stringify(tree, null, '\t' ) );
    
  } // end "loop"

  return tree;
  
} // end function

generateRandomBST.js

/////////////////////////////////////////////////////////////////////////////////////
// GENERATING A RANDOM BINARY SEARCH TREE of a given size (numeric data)

// Next to-do: Generate a BST of a given height ?
/////////////////////////////////////////////////////////////////////////////////////


///////////////// SET UP AS STEP-THROUGH VERSION /////////////////////
document.addEventListener("click", generateBinarySearchTree);

// PARAMETERS FOR FUNCTION:
let valueType = "number"; // or "string" ???
let minValue = 0;
let maxValue = 20;
let numNodes = 8;

// INITIALIZING VARS FOR THE FUNCTION/LOOP:
  let tree = {};
  let currentNode = tree;
  let i = 1;
// INITIALIZE ROOT NODE
  tree.value = getRandomIntInclusive(minValue, maxValue);

function generateBinarySearchTree () {

  // not sure if this is a good condition...
  if (i < numNodes) {
   
    let newVal = getRandomIntInclusive(minValue, maxValue);
    
    console.log("------------------\n i: " + i + ", val: " + newVal);

    // Call insertValueBST for each new value, update tree with new output:
    tree = insertValueBST(newVal, tree);
    
    i++;
    
    console.log("--------------------------------------");
    
  } // end "loop"

  console.log("=================================");
  console.log( JSON.stringify(tree, null, '\t' ) );

  // return tree;
  
} // end function



function insertValueBST (newVal, tree) {
  
  let currentNode = tree;
	
  // not sure if this is a good condition...
  while (currentNode) {
   
    console.log("value: " + newVal);
    console.log("Node " + currentNode.value);

    // If LESS THAN, traverse down the left subtree
    if (newVal < currentNode.value) {
      
      console.log("Newval LESS than cur");
      
      // Insert as the left tchild if no child exists
      if (!currentNode.leftChild) {
       currentNode.leftChild = { value: newVal };
       return tree;
  
      // Otherwise, continue traversing down the left subtree
      } else {
       console.log("Child already exists. Next node: " + currentNode.leftChild.value);
       currentNode = currentNode.leftChild; 
      }
    
    // If GREATER THAN OR EQUAL TO, traverse down the right subtree
    } else if (newVal >= currentNode.value) {
      
      console.log("Newval MORE/EQUAL to cur");
      
      // Insert as the right tchild if no child exists
      if (!currentNode.rightChild) {
       currentNode.rightChild = { value: newVal };
       return tree;
     
      // Otherwise, continue traversing down the right subtree
      } else {
        console.log("Child already exists. Next node: " + currentNode.rightChild.value);
        currentNode = currentNode.rightChild; 
      }
    }
    
    console.log( JSON.stringify(tree, null, '\t' ) );
    
  } // end "loop"

  return tree;
  
} // end function


// via MDN:
function getRandomIntInclusive(min, max) {
  min = Math.ceil(min);
  max = Math.floor(max);
  return Math.floor(Math.random() * (max - min + 1)) + min; //The maximum is inclusive and the minimum is inclusive 
}

initialNotes-generateBinarySearchTree.js

/////////////////////////////////////////////////////////////////////////////////////
// GENERATING A BINARY SEARCH TREE -- INITIAL NOTES
/////////////////////////////////////////////////////////////////////////////////////

// First question: generate it from what? Probably an array of data.
// EXAMPLE ARRAY:
let names = ["Bob", "Gary", "Amy", "Lisa", "Oliver", "Rachel", "Tony", "Sarah"];

// Should they be sorted first...?

/*
// SOLVING IT MANUALLY:

Bob, Gary  -- B is before G, so:
          G
        B

Amy -- before B:

          G
        B
      A
      
Lisa  -- after G:

          G
        B   L
      A
    
Oliver -- after L:

          G
        B   L
      A      O

Rachel -- after O:

          G
        B   L
      A      O
               R
               
Tony -- after R:              

          G
        B   L
      A      O
               R
                T
Sarah -- after R, before t: 

          G
        B   L
      A      O
               R
             S   T

But if the data is in a different order, wouldn't the tree look completely different??? 
    Example: "Bob", "Gary", "Amy", "Lisa"

          G
        B   L
      A

"Amy", "Lisa", "Bob", "Gary"
          A
            L

.. Bob is also after A, but before L  -- replace L with B? / insert B in between A and L:

          A
            B
              L
              
... same for Gary:

          A
            B
              G
                L

// HYPOTHESIS: A binary tree is useless if the data is in order and the root of the tree is the first or last item.
// So sort the data, and then the middle element would be the root of the tree:
// A, b, G, L >> middle item is either B or G:

   B            G
 A  G         B   L
     L       A

// Picturing a cool snake-like pattern if the root is changed letter by letter,
// with the rest of the letters wrapping up/down the tree shape to follow.

// QUESTION: can you do binary search through an array without turning it into a tree?
// If so, what's the advantage of using a tree?

// SEARCH THROUGH ARRAY EXAMPLE -- START TO END:
Goal: find "L" in a given array (whether in order or not, doesn't matter here)
WORST CASE SCENARIO: [A, B, G, L] -- the needle is at the very end of the haystack
Need to check every element: time is O(n) where n is number of elements

// BINARY SEARCH THROUGH ORDERED ARRAY:
1. Start at middle point -- say at B
2. Compare that element to the search term: B is less than the search term L
3. So look to the next element on the right?? *** cut the problem in half again?

Bigger example: [a,b,c,d,e,f,g,h,i,j,k,l,m,n,o,p]
Goal: find L
1. Start at midpoint: array length is 16, look at index 8: H
2. Compare to search term -- H is less than search term L
3. Look at index halfway between 8 and 16: 8+16 /2 is 12: L

WORST CASE SCENARIO: cut problem in half until left with only 2 last choices? 16 > 8 > 4 > 2 > 1 ?

Example: find P:
1. Look at midpoint -- 8: H
2. Look at right half -- 12: L
3. Right half -- 14: N
4. Right half -- 15: O
5. Right half -- 16: P

So for 16 items, up to 5 steps. For 8 items, up to 4 steps. For 4 items, up to 3 steps. (I think?)
Example: [a,b,c,d], Find d:
1. Look at midpoint -- 2: B
2. Look at right half -- 3: C
3. Right half -- 4: D

Or for 2 items, example: [a,b], Find b:
1: Look at midpoint -- a,
2. Right half -- 2: b

Relationship between steps and number of elements:
16 items: 5 steps (4 + 1)
8 items: 4 steps (3 + 1)
4 items: 3 steps (2 + 1)
2 items: 2 steps (1 + 1)

Relationship of 16 to 4, 8 to 3, 4 to 2 ....  2^2=4, 2^3=8, 2^4=16 ... 2^x=n ... x = log2(n)
Time is O( log2(n) ) / logarithmic, in general.

// SIDE QUESTION: For Big O notation, does the base of the logarithm matter? Or only interested in shape of the graph?


// IDEA: Visualizing binary search through array with a tree:
Example: [a,b,c,d,e,f,g,h,i,j,k,l,m,n,o,p], GOAL: Find p
1. Start at midpoint, index 8: H
                
                H
                
2. Right half midpoint, index 12: L
                
                H
                  L
                  
3. Right, index 14: N
                
                H
                  L
                    N
4. Right, index 15: O
                
                H
                  L
                    N
                      O
                       
5. Right, index 16: P
                
                H
                  L
                    N
                      O
                        P

// QUESTION: What's the difference between a binary search algorithm (using an array) vs binary search trees?
// ANSWERS: see notes for day 45 in https://github.com/LearningNerd/100daysofcode/blob/master/README.md


// MORE EXPERIMENTING:
// Given a sorted array.......

// Starting from middle and inserting right-most and left-most nodes, not ideal:
     d
   c   e
  b     f
 a       g
          h 

// Tree of height 4 is possible:

      e
    c    g
  b  d   f h     
 a
 
       d
    b     g
  a  c   f h     
        e
 
     c
  b    f
 a    e  g     
     d    h
     
         f
      b      e
     a c   d  g     
             f h
             
     b
  a    f
      d  g     
     c e  h 
     
     
      d
   b     f
  a c   e g
           h


////////// ATTEMPT AT A BALANCING ALGORITHM: (definitely not done... try again later!) ////////////

1. Divide array into groups of 3, starting from outer edges:

      abc  /  d / efg  <<< easy!   
     
      abc  / def        <<< ??
      abc  /  de / fgh  <<< ??
      
      abc / def / g / hij / klm ? <<< ????
  
2. if length % 3 == 1, middle elem is the root --- only works for length of 7 though :(

            d
       b          f
      a c        e g


OR if length % 3 == 0, middle elem is the root:

            d
       b      e
      a c       f
      
      
         b
      ac   e
           df

*/

insertValueBST.js

/////////////////////////////////////////////////////////////////////////////////////
// INSERTING A VALUE INTO A BINARY SEARCH TREE

// Given a comparable value, iterate through the tree and insert in the first possible location

// NOTE: Is there a case where the value CANNOT be inserted? Or where other values need to be rearranged?
/////////////////////////////////////////////////////////////////////////////////////

///////////////// SET UP AS STEP-THROUGH VERSION /////////////////////
document.addEventListener("click", insertValueBST);

// PARAMETER FOR FUNCTION:
let val = "a";

// INITIALIZING VARS FOR THE FUNCTION/LOOP:
  let tree = {
	"value": "f",
	"leftChild": {
		"value": "d",
		"leftChild": {
			"value": "b"
		},
		"rightChild": {
			"value": "e"
		}
	},
	"rightChild": {
		"value": "h"
	}
};

  let currentNode = tree;
  let valueInserted = false;

function insertValueBST () {

  // not sure if this is a good condition...
  if (currentNode && !valueInserted) {
   
    let newVal = val;
    
    console.log("value: " + val);
    console.log("Node " + currentNode.value);

    // If LESS THAN, traverse down the left subtree
    if (newVal < currentNode.value) {
      
      console.log("Newval LESS than cur");
      
      // Insert as the left tchild if no child exists
      if (!currentNode.leftChild) {
       currentNode.leftChild = { value: newVal };
       valueInserted = true;
  
      // Otherwise, continue traversing down the left subtree
      } else {
        console.log("Child already exists. Next node: " + currentNode.leftChild.value);
       currentNode = currentNode.leftChild; 
      }
    
    // If GREATER THAN OR EQUAL TO, traverse down the right subtree
    } else if (newVal >= currentNode.value) {
      
      console.log("Newval MORE/EQUAL to cur");
      
      // Insert as the right tchild if no child exists
      if (!currentNode.rightChild) {
       currentNode.rightChild = { value: newVal };
        valueInserted = true;
     
      // Otherwise, continue traversing down the right subtree
      } else {
        console.log("Child already exists. Next node: " + currentNode.rightChild.value);
       currentNode = currentNode.rightChild; 
      }
    }
    
    console.log( JSON.stringify(tree, null, '\t' ) );
    
  } // end "loop"

  // return tree;
  
} // end function

queryBST.js

/////////////////////////////////////////////////////////////////////////////////////
// FINDING A VALUE IN A BINARY SEARCH TREE 
//
// Given a value and a BST, find and return that value (or null if it doesn't exist)
//
// Later version: connect these values to other data,
// say for indexing people by their phone number, etc.
/////////////////////////////////////////////////////////////////////////////////////

/*
VERSION 1 -- 


Logic: compare query to node's value -- if less than: next node = left child
                                    -- otherwise, next node = right child
                                     -- if it matches, return it!
*/




///////////////// SET UP AS STEP-THROUGH VERSION /////////////////////
document.addEventListener("click", queryBST);

// PARAMETER FOR FUNCTION:
let query = "c";

let bst = {
	"value": "f",
	"leftChild": {
		"value": "d",
		"leftChild": {
			"value": "b",
			"leftChild": {
				"value": "a"
			},
			"rightChild": {
				"value": "c"
			}
		},
		"rightChild": {
			"value": "e"
		}
	},
	"rightChild": {
		"value": "h",
		"leftChild": {
			"value": "g"
		}
	}
};

// INITIALIZING VARS FOR THE FUNCTION/LOOP:
  let currentNode = bst;
  
function queryBST() {
  
  if (currentNode) {
    
   if (query === currentNode.value) {
     console.log("Found the value: " + currentNode.value);
     //return currentNode.value;
   } else if (query < currentNode.value) {
     console.log(query + " < " + currentNode.value);
     currentNode = currentNode.leftChild;
   } else {     
     console.log(query + " > " + currentNode.value);
     currentNode = currentNode.rightChild;
   }
    
  } else {
    console.log("Sorry, we're fresh outa nodes!");
    //return null;
  } // end if/else(currentNode)
  
} // end function