### Binary Tree

 // Binary Search Trees search in logarithmic time since we halve // after every search operation. i.e. on average operations are able // to skip about half the tree. each insertion, deletion or lookup takes // time proportional to the log of items stored in the tree. // // this is better than linear time required to find items by key in unsorted array // but slower than corresponding operations on a hash table // root node - level 0 // first leaf node - level 1 // second '' - level 2 // ... // .. // . class Node { constructor(data, left = null, right = null) { this.data = data; this.left = left; // points to left node this.right = right; // points to right node } } // Data lower than current node goes to left of current node // Data greater than current node goes to right of current node class BST { constructor() { this.root = null; // top of tree } add(data) { const node = this.root; if (node === null) { // if this is first node, node will be null this.root = new Node(data); return; } else { const searchTree = function(node) { if (data < node.data) { if (node.left === null) { node.left = new Node(data); return; } else if (node.left !== null) { return searchTree(node.left); } } else if (data > node.data) { if (node.right === null) { node.right = new Node(data); return; } else if (node.right !== null) { return searchTree(node.right); } } else { // if data is neither less than or greater than any node it's already in tree return null; } } return searchTree(node); } } findMin() { let current = this.root; while (current.left !== null) { // will stop once current node doesn't point to a left current = current.left; } return current.data; } findMax() { let current = this.root; while (current.right !== null) { current = current.right; } return current.data; } find(data) { let current = this.root; while (current.data !== data) { if (data < current.data) { current = current.left; } else { current = current.right; } if (current === null) { return null; } } return current; } isPresent(data) { let current = this.root; while (current) { if (data === current.data) { return true; } else if (data < current.data) { current = current.left; } else { current = current.right; } } return false; } remove(data) { // function signature // node: starting node // data: value to delete from tree const removeNode = function(node, data) { // if node is null we have an empty tree; return if (node == null) { return null; } // check if we found that data in the tree // if we did, check if that node has children if (data == node.data) { // 3 cases: 1. node has no children; 2. node has 1 child (left or right); 3. node has two children // 1. if node has no children if (node.left == null && node.right == null) { // set the reference to the node that had that data to null; i.e. delete it. return null; } // 2. if node has no left children if (node.left == null) { // replace the current node with whatever's on the right // to keep correct tree structure return node.right; } // 2. node has no right child if (node.right == null) { // replace current node with left node return node.left; } // 3. if node has two children // // go to next largest node var tempNode = node.right; while (tempNode.left !== null) { // keep going down all the left nodes // until you hit the last left node // that node is larger than the current node but less than node.right // i.e. that's the one we use to replace original node that was passed in as arg tempNode = tempNode.left; } // replace current node data with tempNode data from left-most node node.data = tempNode.data; // replace right node subtree with result from recursive function call, deleting tempNode.data, i.e. left-most node node.right = removeNode(node.right, tempNode.data); // this says 'start at right node and look for tempNode.data and delete it' return node; } else if (data < node.data) { node.left = removeNode(node.left, data); return node; } else { node.right = removeNode(node.right, data); return node; } } // function call // pass in root (always start with root) and data that we're searching for this.root = removeNode(this.root, data); } // minHeight is distance from root node to first leaf node without 2 children // e.g. from root node (level 0) to next leaf node with just one child or none (level 1) = 1 findMinHeight(node = this.root) { // if tree is empty return -1 if (node == null) { return -1; }; // recurvsive calls // eventually one of these will return -1 as above // i.e. one of these will eventually point to an empty child node // i.e. the node will not have children let left = this.findMinHeight(node.left); let right = this.findMinHeight(node.right); if (left < right) { return left + 1; } else { return right + 1; } } // distance from root node to bottom-most node of tree findMaxHeight(node = this.root) { if (node == null) { return -1; } // eventually one of these will return -1 let left = this.findMaxHeight(node.left); let right = this.findMaxHeight(node.right); if (left > right) { return left + 1; } else { return right + 1; } } // a balanced tree is a tree where the difference between minHeight and maxHeight differ by at most 1 // balanced tree: maxHeight - minHeight <= 1 isBalanced() { // if min height and max height differ by only one, tree is balanced // minHeight >= maxHeight - 1; same as maxHeight - minHeight <= 1 return (this.findMinHeight() >= this.findMaxHeight() - 1); } /* Tree Traversal Methods */ // used to traverse tree and find values within tree /* depth-first search: tree is explored as deeply as possible before search continues on another subtree three ways to do depth-first search: 1. inOrder traversal: begin search at left-most node and end at right-most node. adds numbers in order 2. preOrder traversal: explore root nodes before the leaves. searches one subtree fully (e.g. root.left) before moving on to next subtree (e.g. root.right) 3. postOrder traversal: explores leaf nodes before roots. also searches by subtree fully up to root node before moving on to next subtree. breadth-first search: search explores all nodes in a given level within a tree before moving on to next level first level 0 then level 1 .... etc. */ inOrder() { // just check if tree even exists // if not return null if (this.root == null) { return null; } else { var result = new Array(); function traverseInOrder(node) { // this says, 'if left node exists, run this function. uses short circuit hacking node.left && traverseInOrder(node.left); result.push(node.data); // if right node exists, run this function node.right && traverseInOrder(node.right); } traverseInOrder(this.root); return result; } } preOrder() { if (this.root == null) { return null; } else { var result = new Array(); function traversePreOrder(node) { result.push(node.data); node.left && traversePreOrder(node.left); node.right && traversePreoOrder(node.right); } traversePreOrder(this.root); return result; } } postOrder() { if (this.root == null) { return null; } else { var result = new Array(); function traversePostOrder(node) { node.left && traversePostOrder(node.left); node.right && traversePostOrder(node.right); result.push(node.data); } traversePostOrder(this.root); return result; } } levelOrder() { //eventually this will be returned let result = []; // temp array we are using. eventually elements from here // will be put onto results array let Q = []; if (this.root != null) { Q.push(this.root); while (Q.length > 0) { // as long as there's something in q let node = Q.shift(); // dequeu first item result.push(node.data); if (node.left != null) { Q.push(node.left); // push next level left node } if (node.right != null) { Q.push(node.right); // push next level right node } } return result; } else { return null; } } }