Chapter 4 - Trees and Graphs.ipynb

{
 "cells": [
  {
   "cell_type": "code",
   "execution_count": 8,
   "metadata": {},
   "outputs": [],
   "source": [
    "class LLNode {\n",
    "    constructor(data, next = null) {\n",
    "        this.data = data;\n",
    "        this.next = null;\n",
    "    }\n",
    "}\n",
    "\n",
    "class LinkedList {\n",
    "    constructor() {\n",
    "        this.head = null;\n",
    "    }\n",
    "    \n",
    "    add(data) {\n",
    "        const newNode = new LLNode(data);\n",
    "        \n",
    "        if(this.head === null) {\n",
    "            this.head = newNode;\n",
    "        }\n",
    "        else {\n",
    "            newNode.next = this.head;\n",
    "            this.head = newNode;\n",
    "        }\n",
    "    }\n",
    "    \n",
    "    *values() {\n",
    "        let current = this.head;\n",
    "        while(current !== null) {\n",
    "            yield current.data;\n",
    "            current = current.next;\n",
    "        }\n",
    "    }\n",
    "    \n",
    "    [Symbol.iterator]() {\n",
    "        return this.values();\n",
    "    }\n",
    "}\n",
    "\n",
    "class Vertex {\n",
    "    constructor(key) {\n",
    "        this.id = key;\n",
    "        this.connectedTo = new Map();\n",
    "        this.dist = null;\n",
    "        this.predecessor = null;\n",
    "        this.colour = 'white';\n",
    "        this.discovery = null;\n",
    "        this.finish = null;\n",
    "    }\n",
    "    \n",
    "    addNeighbor(nbr, weight = 0) {\n",
    "        this.connectedTo.set(nbr, weight);\n",
    "    }\n",
    "    \n",
    "    getConnections() {\n",
    "        return this.connectedTo;\n",
    "    }\n",
    "    \n",
    "    getId() {\n",
    "        return this.id;\n",
    "    }\n",
    "    \n",
    "    getWeight(nbr) {\n",
    "        return this.connectedTo.get(nbr);\n",
    "    }\n",
    "    \n",
    "    get color() {\n",
    "        return this.colour;\n",
    "    }\n",
    "    \n",
    "    set color(value) {\n",
    "        this.colour = value;\n",
    "    }\n",
    "    \n",
    "    get distance() {\n",
    "        return this.dist;\n",
    "    }\n",
    "    \n",
    "    set distance(value) {\n",
    "        this.dist = value;\n",
    "    }\n",
    "    \n",
    "    get pred() {\n",
    "        return this.predecessor;\n",
    "    }\n",
    "    \n",
    "    set pred(value) {\n",
    "        this.predecessor = value;\n",
    "    }\n",
    "    \n",
    "    get disc() {\n",
    "        return this.discovery;\n",
    "    }\n",
    "    \n",
    "    set disc(value) {\n",
    "        this.discovery = value;\n",
    "    }\n",
    "    \n",
    "    get fin() {\n",
    "        return this.finish;\n",
    "    }\n",
    "    \n",
    "    set fin(value) {\n",
    "        this.finish = value;\n",
    "    }\n",
    "}\n",
    "\n",
    "class Graph {\n",
    "    constructor(){\n",
    "        this.vertList = new Map();\n",
    "        this.numVertices = 0;\n",
    "    }\n",
    "    \n",
    "    addVertex(key) {\n",
    "        this.numVertices++;\n",
    "        const newVertex = new Vertex(key);\n",
    "        this.vertList.set(key, newVertex);\n",
    "        return newVertex;\n",
    "    }\n",
    "    \n",
    "    getVertex(key) {\n",
    "        return this.vertList.has(key) ? this.vertList.get(key) : undefined;\n",
    "    }\n",
    "    \n",
    "    addEdge(from, to, weight = 0) {\n",
    "        if(! this.vertList.has(from) ) {\n",
    "            this.addVertex(from);\n",
    "        }\n",
    "        if(! this.vertList.has(to) ) {\n",
    "            this.addVertex(to);\n",
    "        }\n",
    "        this.vertList.get(from).addNeighbor(this.vertList.get(to), weight);\n",
    "    }\n",
    "    \n",
    "    getVertices() {\n",
    "        return this.vertList.keys();\n",
    "    }\n",
    "    \n",
    "    *values() {\n",
    "        for(let [key, value] of this.vertList) {\n",
    "            yield value;\n",
    "        };\n",
    "    }\n",
    "    \n",
    "    [Symbol.iterator]() {\n",
    "        return this.values();\n",
    "    }\n",
    "}\n",
    "\n",
    "class Queue {\n",
    "    constructor() {\n",
    "        this.items = [];\n",
    "        this.size = 0;\n",
    "    }\n",
    "    \n",
    "    enqueue(item) {\n",
    "        this.items.push(item);\n",
    "        this.size++;\n",
    "    }\n",
    "    \n",
    "    dequeue(item) {\n",
    "        this.size--;\n",
    "        return this.items.shift();\n",
    "    }\n",
    "    \n",
    "    get length() {\n",
    "        return this.size;\n",
    "    }\n",
    "    \n",
    "    isEmpty() {\n",
    "        return this.size === 0;\n",
    "    }\n",
    "}\n",
    "\n",
    "// starting at any node\n",
    "// follow its predecessor until it reaches the root\n",
    "function traverse(node) {\n",
    "    let x = node;\n",
    "    while(x.pred !== null) {\n",
    "        console.log(x.getId());\n",
    "        x = x.pred;\n",
    "    }\n",
    "    console.log(x.getId());\n",
    "}\n",
    "\n",
    "class TreeNode {\n",
    "    constructor(key, val, left = null, right = null, parent = null) {\n",
    "        this.key = key;\n",
    "        this.payload = val;\n",
    "        this.left = left;\n",
    "        this.right = right;\n",
    "        this.parent = parent;\n",
    "    }\n",
    "    \n",
    "    hasLeftChild() {\n",
    "        return this.left !== null;\n",
    "    }\n",
    "    \n",
    "    hasRightChild() {\n",
    "        return this.right !== null;\n",
    "    }\n",
    "    \n",
    "    isLeftChild() {\n",
    "        return this.parent !== null && this.parent.left === this;\n",
    "    }\n",
    "    \n",
    "    isRightChild() {\n",
    "        return this.parent !== null && this.parent.right === this;\n",
    "    }\n",
    "    \n",
    "    isRoot() {\n",
    "        return this.parent === null;\n",
    "    }\n",
    "    \n",
    "    isLeaf() {\n",
    "        return !(this.hasAnyChildren() );\n",
    "    }\n",
    "    \n",
    "    hasAnyChildren() {\n",
    "        return this.hasLeftChild() || this.hasRightChild();\n",
    "    }\n",
    "    \n",
    "    hasBothChildren() {\n",
    "        return this.hasLeftChild() && this.hasRightChild();\n",
    "    }\n",
    "    \n",
    "    replaceNodeData(key, value, left, right) {\n",
    "        this.key = key;\n",
    "        this.payload = value;\n",
    "        this.left = left;\n",
    "        this.right = right;\n",
    "        if(this.hasLeftChild()) {\n",
    "            this.left.parent = this;\n",
    "        }\n",
    "        if(this.hasRightChild()) {\n",
    "            this.right.parent = this;\n",
    "        }\n",
    "    }\n",
    "    \n",
    "    findSuccessor() {\n",
    "        let successor;\n",
    "        // if current node has a right subtree, find the minimum of \n",
    "        // right subtree\n",
    "        if(this.hasRightChild()) {\n",
    "            successor = this.right.findMin();\n",
    "        }\n",
    "        // else if it does not have a right subtree, then it will have an ancestor\n",
    "        // who is a left child of its parent\n",
    "        // else if it is a right child, keep going up the tree\n",
    "        else {\n",
    "            if(this.parent !== null) {\n",
    "                if(this.isLeftChild()) {\n",
    "                    successor = this.parent;\n",
    "                }\n",
    "                else {\n",
    "                    // we remove our node from the tree temporarily\n",
    "                    // find the successor again\n",
    "                    // then add it back\n",
    "                    // this is because we call findSuccessor on the parent\n",
    "                    // and since it has a rightChild (previous node), then it will assign\n",
    "                    // the successor to the current node\n",
    "                    // so we remove it temporarily until we find the correct node!\n",
    "                    this.parent.right = null;\n",
    "                    successor = this.parent.findSucessor();\n",
    "                    this.parent.right = this;\n",
    "                }\n",
    "            }\n",
    "        }\n",
    "        return successor;\n",
    "    }\n",
    "    \n",
    "    // the minimum in a binary search tree is the leftmost node in the\n",
    "    // tree\n",
    "    findMin() {\n",
    "        let current = this;\n",
    "        while(current.hasLeftChild()) {\n",
    "            current = current.left;\n",
    "        }\n",
    "        return current;\n",
    "    }\n",
    "    \n",
    "    spliceOut() {\n",
    "        // if the node is a leaf, then change the parent's child\n",
    "        // reference to be null depending on whether it was a \n",
    "        // right or left child\n",
    "        if(this.isLeaf()) {\n",
    "            if(this.isLeftChild()) {\n",
    "                this.parent.left = null;\n",
    "            }\n",
    "            else {\n",
    "                this.parent.right = null;\n",
    "            }\n",
    "        }\n",
    "        else if (this.hasAnyChild()) {\n",
    "            if(this.hasLeftChild()) {\n",
    "                if(this.isLeftChild()) {\n",
    "                    this.parent.left = this.left;\n",
    "                }\n",
    "                else {\n",
    "                    this.parent.right = this.right;\n",
    "                }\n",
    "                this.left.parent = this.parent;\n",
    "            }\n",
    "            else {\n",
    "                if(this.isleftChild()) {\n",
    "                    this.parent.left = this.right;\n",
    "                }\n",
    "                else {\n",
    "                    this.parent.right = this.right;\n",
    "                }\n",
    "                this.right.parent = this.parent;\n",
    "            }\n",
    "        }\n",
    "    }\n",
    "}\n",
    "\n",
    "\n",
    "const root = Symbol('root');\n",
    "\n",
    "class BinarySearchTree {\n",
    "    constructor() {\n",
    "        this[root] = null;\n",
    "        this.size = 0;\n",
    "    }\n",
    "    \n",
    "    get length() {\n",
    "        return this.size;\n",
    "    }\n",
    "    \n",
    "    inOrder(node = this[root]) {\n",
    "        if(node !== null) {\n",
    "            this.inOrder(node.left);\n",
    "            console.log(node.payload);\n",
    "            this.inOrder(node.right);\n",
    "        }\n",
    "    }\n",
    "    \n",
    "    // inserting items into bst\n",
    "    put(key, val) {\n",
    "        // if the tree is not empty, then find the correct position\n",
    "        // for it\n",
    "        if(this[root] !== null) {\n",
    "            this._put(key, val, this[root]);\n",
    "        }\n",
    "        // else if the tree is empty, just put the new node\n",
    "        // as the root of the tree\n",
    "        else {\n",
    "            this[root] = new TreeNode(key, val);\n",
    "        }\n",
    "        this.size++;\n",
    "    }\n",
    "    \n",
    "    // recursive function that helps find the correct position for the\n",
    "    // new item.\n",
    "    // it will move left or right depending on value of new node and parent\n",
    "    // until it reaches a node that does not have a child or both children\n",
    "    _put(key, val, currentNode) {\n",
    "        // if child key < parent key\n",
    "        if (key < currentNode.key) {\n",
    "            // if parent has a left child, recurse on the left\n",
    "            if(currentNode.hasLeftChild()) {\n",
    "                this._put(key, val, currentNode.left);\n",
    "            }\n",
    "            // else the currentnode is now the parent\n",
    "            // and the new node is now its left child\n",
    "            else {\n",
    "                currentNode.left = new TreeNode(key, val, null, null, currentNode);\n",
    "            }\n",
    "        }\n",
    "        // else if child key > parent key\n",
    "        else {\n",
    "            // if parent has a right child, recurse on right\n",
    "            if(currentNode.hasRightChild()) {\n",
    "               this._put(key, val, currentNode.right);\n",
    "            }\n",
    "            // else current node is now the parent\n",
    "            // and the new node is now its left child\n",
    "            else {\n",
    "                currentNode.right = new TreeNode(key, val, null, null, currentNode);\n",
    "            }\n",
    "        }\n",
    "    }\n",
    "    \n",
    "    \n",
    "    // returns the value of the node at the current key\n",
    "    // if the tree is not empty, calls a recursive function _get\n",
    "    // to traverse the tree to find it\n",
    "    get(key) {\n",
    "        if(this[root] === null) {\n",
    "            return undefined;\n",
    "        }\n",
    "        const result = this._get(key, this[root]);\n",
    "        return result ? result : undefined;\n",
    "    }\n",
    "    \n",
    "    // recursive function that will traverse the tree until it finds the key\n",
    "    // if the key is less than the parent, go left\n",
    "    // if the key is greater than the parent, go right\n",
    "    _get(key, currentNode) {\n",
    "        if(currentNode === null) {\n",
    "            return undefined;\n",
    "        }\n",
    "        else if(currentNode.key === key) {\n",
    "            return currentNode;\n",
    "        }\n",
    "        else if (key < currentNode.key) {\n",
    "            return this._get(key, currentNode.left);\n",
    "        }\n",
    "        else {\n",
    "            return this._get(key, currentNode.right);\n",
    "        }\n",
    "    }\n",
    "    \n",
    "    del(key) {\n",
    "        if(this.size > 1) {\n",
    "            const nodeToRemove = this._get(key, this[root]);\n",
    "            if(nodeToRemove) {\n",
    "                this.remove(nodeToRemove);\n",
    "                this.size--;\n",
    "            }\n",
    "            else {\n",
    "                return undefined;\n",
    "            }\n",
    "        }\n",
    "        else if(this.size === 1 && this[root].key === key) {\n",
    "            this[root] = null;\n",
    "            this.size--;\n",
    "        }\n",
    "        else {\n",
    "            return undefined;\n",
    "        }\n",
    "    }\n",
    "    \n",
    "    remove(currentNode) {\n",
    "        // current node is a leaf, then just have its parent point\n",
    "        // to null\n",
    "        if(currentNode.isLeaf()) {\n",
    "            if (currentNode.isLeftChild()) {\n",
    "                currentNode.parent.left = null;\n",
    "            }\n",
    "            else {\n",
    "                currentNode.parent.right = null;\n",
    "            }\n",
    "        }\n",
    "        // else if currentnode has 2 children\n",
    "        // find the successor, splice it out\n",
    "        // and replace currentnode with successor\n",
    "        else if(currentNode.hasBothChildren()) {\n",
    "            let successor = currentNode.findSuccessor();\n",
    "            successor.spliceOut();\n",
    "            currentNode.key = successor.key;\n",
    "            currentNode.payload = successor.payload;\n",
    "        }\n",
    "        // node has only 1 child\n",
    "        else {\n",
    "            // if current node has a  left child\n",
    "            if(currentNode.hasLeftChild()) {\n",
    "                // if current node is the left child with a left child\n",
    "                if(currentNode.isLeftChild()) {\n",
    "                    currentNode.left.parent = currentNode.parent;\n",
    "                    currentNode.parent.left = currentNode.left;\n",
    "                }\n",
    "                // if current node is the right child with a left child\n",
    "                else if (currentNode.isRightChild()) {\n",
    "                    currentNode.left.parent = currentNode.parent;\n",
    "                    currentNode.parent.right = currentNode.left;\n",
    "                }\n",
    "                // if currentNode is the root\n",
    "                else {\n",
    "                    currentNode.replaceNodeData(currentNode.left.key,\n",
    "                                                currentNode.left.payload,\n",
    "                                                currentNode.left.left,\n",
    "                                                currentNode.left.right)\n",
    "                }\n",
    "            }\n",
    "            // if current node has a right child\n",
    "            else {\n",
    "                // if current node is a left child with a right child\n",
    "                if(currentNode.isLeftChild()) {\n",
    "                    currentNode.right.parent = currentNode.parent;\n",
    "                    currentNode.parent.left = currentNode.right;\n",
    "                }\n",
    "                // if current node is a left child with a right child\n",
    "                else if(currentNode.isRightChild()) {\n",
    "                    currentNode.right.parent = currentNode.parent;\n",
    "                    currentNode.parent.right = currentNode.right;\n",
    "                }\n",
    "                // if currentNode is the root\n",
    "                else {\n",
    "                    currentNode.replaceNodeData(currentNode.right.key,\n",
    "                                                currentNode.right.payload,\n",
    "                                                currentNode.right.left,\n",
    "                                                currentNode.right.right)\n",
    "                }\n",
    "            }\n",
    "        }\n",
    "    }\n",
    "}\n",
    "\n",
    "function inOrder(node) {\n",
    "    if(node !== null) {\n",
    "        inOrder(node.left);\n",
    "        console.log(node.payload);\n",
    "        inOrder(node.right);\n",
    "    }\n",
    "}\n",
    "\n",
    "function preOrder(node) {\n",
    "    if(node !== null) {\n",
    "        console.log(node.payload);\n",
    "        preOrder(node.left);\n",
    "        preOrder(node.right);\n",
    "    }\n",
    "}\n",
    "\n",
    "function postOrder(node) {\n",
    "    if(node !== null) {\n",
    "        postOrder(node.left);\n",
    "        postOrder(node.right);\n",
    "        console.log(node.payload);\n",
    "    }\n",
    "}"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## 4.1 Route Between Nodes\n",
    "* Given a directed graph, design an algorithm to find out whether there is a route between two nodes\n",
    "* Hints: \n",
    "    - 127"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 28,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "true"
      ]
     },
     "execution_count": 28,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "function bfs(start) {\n",
    "    let q = new Queue();\n",
    "    start.distance = 0;\n",
    "    start.pred = null;\n",
    "    q.enqueue(start);\n",
    "    \n",
    "    while( q.size > 0 ) {\n",
    "        let currentVertex = q.dequeue();\n",
    "        for(let [nbr, weight] of currentVertex.getConnections()) {\n",
    "            if(nbr.color === 'white') {\n",
    "                nbr.color = 'gray';\n",
    "                nbr.distance = currentVertex.distance + 1;\n",
    "                nbr.pred = currentVertex;\n",
    "                q.enqueue(nbr);\n",
    "            }\n",
    "        }\n",
    "        currentVertex.color = 'black';\n",
    "    }\n",
    "}\n",
    "\n",
    "function isRoute(start, destination) {\n",
    "    while(destination.pred !== null) {\n",
    "        destination = destination.pred;\n",
    "    }\n",
    "    return start === destination;\n",
    "}\n",
    "\n",
    "var g = new Graph();\n",
    "g.addEdge('source', 'mid');\n",
    "g.addEdge('mid', 'midLeft');\n",
    "g.addEdge('midLeft', 'destination');\n",
    "g.addEdge('mid','midRight');\n",
    "\n",
    "bfs(g.getVertex('source'));\n",
    "isRoute(g.getVertex('source'), g.getVertex('destination'));"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Book Solutions:\n",
    "* can be solved by any graph traversal algorithm such as DFS or BFS\n",
    "* solution:\n",
    "    1. start at one of the 2 nodes\n",
    "    2. if the node is found during traversal, return true\n",
    "* Analysis:\n",
    "    - time complexity is equal to the time complexity of the traversal, so O(V + E)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 54,
   "metadata": {},
   "outputs": [],
   "source": [
    "function bfs(start, end) {\n",
    "    let q = new Queue();\n",
    "    start.distance = 0;\n",
    "    start.pred = null;\n",
    "    q.enqueue(start);\n",
    "    \n",
    "    while( q.size > 0 ) {\n",
    "        let currentVertex = q.dequeue();\n",
    "        for(let [nbr, weight] of currentVertex.getConnections()) {\n",
    "            if(nbr === end) {\n",
    "                return true;\n",
    "            }\n",
    "            if(nbr.color === 'white') {\n",
    "                nbr.color = 'gray';\n",
    "                nbr.distance = currentVertex.distance + 1;\n",
    "                nbr.pred = currentVertex;\n",
    "                q.enqueue(nbr);\n",
    "            }\n",
    "        }\n",
    "        currentVertex.color = 'black';\n",
    "    }\n",
    "    return false;\n",
    "}\n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## 4.2 Minimal Tree\n",
    "* Given a sorted (increasing order) array with unique integer elements, write an algorithm to create a binary search tree with minimal height."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 29,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "1\n",
      "2\n",
      "3\n",
      "4\n",
      "5\n",
      "6\n",
      "7\n",
      "8\n",
      "9\n"
     ]
    }
   ],
   "source": [
    "var array = [1, 2, 3, 4, 5, 6, 7, 8, 9];\n",
    "var tree = new BinarySearchTree();\n",
    "\n",
    "function minTree(array) {\n",
    "    if(array.length === 0) { return; }\n",
    "    let mid = Math.trunc(array.length / 2);\n",
    "    tree.put(array[mid], array[mid]);\n",
    "    \n",
    "    // left side\n",
    "    minTree(array.slice(0, mid));\n",
    "    // right side\n",
    "    minTree(array.slice(mid + 1));\n",
    "}\n",
    "\n",
    "minTree(array);\n",
    "inOrder(tree.get(5));"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Book Solutions:\n",
    "* solution:\n",
    "    1. insert middle element of array into tree\n",
    "    2. insert into left subtree left subarray elements\n",
    "    3. do the same with the right\n",
    "* this solution is faster than my solution b/c it does not insert it into the binary search tree normally where an insertion is O( log n)\n",
    "    - my answer is O(n log n) b/c i was inserting each array into the BST\n",
    "    - in this solution, we create a mini tree with the current node as the root and 2 nodes for its left and right and we build up the whole tree\n",
    "    - in essence, we build the trees in parts and then put the whole thing together so that it reduces extra traversals"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "function createMinimalBST(array) {\n",
    "    return _createMinimalBST(array, 0, array.length - 1);\n",
    "}\n",
    "\n",
    "function _createMinimalBST(arr, start, end) {\n",
    "    if(end < start) { return null; }\n",
    "    let mid = Math.trunc( (start + end) / 2);\n",
    "    let n = new TreeNode(arr[mid]);\n",
    "    n.left = _createMinimalBST(arr, start, mid - 1);\n",
    "    n.right = _createMinimalBST(arr, mid + 1, end);\n",
    "    return n;\n",
    "}"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## 4.3 List of Depths"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 46,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "0\n",
      "[ TreeNode {\n",
      "    key: 'A',\n",
      "    payload: 'A',\n",
      "    left: \n",
      "     TreeNode {\n",
      "       key: 'B',\n",
      "       payload: 'B',\n",
      "       left: [Object],\n",
      "       right: [Object],\n",
      "       parent: null,\n",
      "       distance: 1 },\n",
      "    right: \n",
      "     TreeNode {\n",
      "       key: 'C',\n",
      "       payload: 'C',\n",
      "       left: null,\n",
      "       right: null,\n",
      "       parent: null,\n",
      "       distance: 1 },\n",
      "    parent: null,\n",
      "    distance: 0 } ]\n",
      "\n",
      "\n",
      "1\n",
      "[ TreeNode {\n",
      "    key: 'C',\n",
      "    payload: 'C',\n",
      "    left: null,\n",
      "    right: null,\n",
      "    parent: null,\n",
      "    distance: 1 },\n",
      "  TreeNode {\n",
      "    key: 'B',\n",
      "    payload: 'B',\n",
      "    left: \n",
      "     TreeNode {\n",
      "       key: 'D',\n",
      "       payload: 'D',\n",
      "       left: null,\n",
      "       right: null,\n",
      "       parent: null,\n",
      "       distance: 2 },\n",
      "    right: \n",
      "     TreeNode {\n",
      "       key: 'E',\n",
      "       payload: 'E',\n",
      "       left: null,\n",
      "       right: null,\n",
      "       parent: null,\n",
      "       distance: 2 },\n",
      "    parent: null,\n",
      "    distance: 1 } ]\n",
      "\n",
      "\n",
      "2\n",
      "[ TreeNode {\n",
      "    key: 'E',\n",
      "    payload: 'E',\n",
      "    left: null,\n",
      "    right: null,\n",
      "    parent: null,\n",
      "    distance: 2 },\n",
      "  TreeNode {\n",
      "    key: 'D',\n",
      "    payload: 'D',\n",
      "    left: null,\n",
      "    right: null,\n",
      "    parent: null,\n",
      "    distance: 2 } ]\n",
      "\n",
      "\n"
     ]
    }
   ],
   "source": [
    "function listDepths(start) {\n",
    "    let levels = {};\n",
    "    let q = new Queue();\n",
    "    start.distance = 0;\n",
    "    q.enqueue(start);\n",
    "    \n",
    "    while( !q.isEmpty() ) {\n",
    "        let current = q.dequeue();\n",
    "        let dist = current.distance;\n",
    "        if(levels[dist] === undefined) {\n",
    "            levels[dist] = new LinkedList();\n",
    "        }\n",
    "        levels[dist].add(current);\n",
    "        if(current.left !== null) {\n",
    "            current.left.distance = dist + 1;\n",
    "            q.enqueue(current.left);\n",
    "        }\n",
    "        if(current.right !== null) {\n",
    "            current.right.distance = dist + 1;\n",
    "            q.enqueue(current.right);\n",
    "        }\n",
    "    }\n",
    "    return levels;\n",
    "}\n",
    "\n",
    "var r = new TreeNode('A', 'A');\n",
    "var B = new TreeNode('B', 'B');\n",
    "var C = new TreeNode('C', 'C');\n",
    "var D = new TreeNode('D', 'D');\n",
    "var E = new TreeNode('E', 'E');\n",
    "\n",
    "r.left = B;\n",
    "r.right = C;\n",
    "B.left = D;\n",
    "B.right = E;\n",
    "\n",
    "var levels = listDepths(r);\n",
    "for(let level in levels) {\n",
    "    console.log(level)\n",
    "    console.log([...levels[level]])\n",
    "    console.log('\\n')\n",
    "}\n",
    "// remember linked lists are inserted at the head so the \n",
    "// first item inserted is at the end of the linkedlist \n",
    "// while the last item inserted is at the front of the linkedlist"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Book Solutions:\n",
    "* essentially the same solution as what we did\n",
    "* analysis: \n",
    "    - O(V + E) for bfs\n",
    "    - O(1) for creating and inserting into a new Linked List\n",
    "    - O(n) space b/c have to return n nodes"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## 4.4 Check Balanced"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 61,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "{ node: 'F', bf: 0 }\n",
      "{ node: 'E', bf: 1 }\n",
      "{ node: 'D', bf: 2 }\n",
      "{ node: 'B', bf: 3 }\n",
      "{ node: 'C', bf: 0 }\n",
      "{ node: 'A', bf: 3 }\n",
      "{ balanceFactor: 3 }\n",
      "false\n",
      "{ node: 2, bf: 0 }\n",
      "{ node: 3, bf: 0 }\n",
      "{ node: 1, bf: 0 }\n",
      "{ balanceFactor: 0 }\n",
      "true\n"
     ]
    }
   ],
   "source": [
    "function isBalanced(start) {\n",
    "    let balanceFactor = this.postOrder(start);\n",
    "    console.log({balanceFactor})\n",
    "    return balanceFactor <= 1;\n",
    "}\n",
    "\n",
    "function postOrder(node) {\n",
    "    if(node !== null) {\n",
    "        let left = postOrder(node.left) + 1;\n",
    "        let right = postOrder(node.right) + 1;\n",
    "        console.log({node: node.key, bf: Math.abs(left - right)})\n",
    "        return Math.abs(left - right);\n",
    "    }\n",
    "    else {\n",
    "        return -1;\n",
    "    }\n",
    "}\n",
    "\n",
    "//         r\n",
    "//        / \\\n",
    "//       B   C\n",
    "//      /\n",
    "//     D\n",
    "//    /\n",
    "//   E\n",
    "//  /\n",
    "// F\n",
    "var r = new TreeNode('A', 'A');\n",
    "var B = new TreeNode('B', 'B');\n",
    "var C = new TreeNode('C', 'C');\n",
    "var D = new TreeNode('D', 'D');\n",
    "var E = new TreeNode('E', 'E');\n",
    "var F = new TreeNode('F', 'F');\n",
    "\n",
    "r.left = B;\n",
    "r.right = C;\n",
    "B.left = D;\n",
    "D.left = E;\n",
    "E.left = F;\n",
    "\n",
    "console.log(isBalanced(r));\n",
    "\n",
    "var rr = new TreeNode(1,1);\n",
    "var bb = new TreeNode(2,2);\n",
    "var cc = new TreeNode(3,3);\n",
    "\n",
    "rr.left = bb;\n",
    "rr.right = cc;\n",
    "\n",
    "console.log(isBalanced(rr));"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Book Solutions:\n",
    "* solution:\n",
    "    - 1. modified version of postorder traversal\n",
    "    - 2. it will be able to tell us the height of the left and right subtrees as it goes down the tree\n",
    "        - since this is postorder traversal, it will go down first, then when we go back up the tree again recursively, it will calculate the values\n",
    "    - 3. if the tree is not balanced, i.e. its balance is off by more than 1, then return an error\n",
    "* not really any different from my code!"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 58,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "false\n",
      "true\n"
     ]
    }
   ],
   "source": [
    "function isBalanced2(root) {\n",
    "    return checkHeight(root) !== Number.MIN_VALUE;\n",
    "}\n",
    "\n",
    "function checkHeight(node) {\n",
    "    if(node == null) {\n",
    "        return -1;\n",
    "    }\n",
    "    \n",
    "    let leftHeight = checkHeight(node.left);\n",
    "    if(leftHeight === Number.MIN_VALUE) { return Number.MIN_VALUE; }\n",
    "    \n",
    "    let rightHeight = checkHeight(node.right);\n",
    "    if(rightHeight === Number.MIN_VALUE) { return Number.MIN_VALUE; }\n",
    "    \n",
    "    let heightDiff = leftHeight - rightHeight;\n",
    "    if(Math.abs(heightDiff) > 1) {\n",
    "        return Number.MIN_VALUE;\n",
    "    }\n",
    "    else {\n",
    "        return Math.max(leftHeight, rightHeight) + 1;\n",
    "    }\n",
    "}\n",
    "\n",
    "var r = new TreeNode('A', 'A');\n",
    "var B = new TreeNode('B', 'B');\n",
    "var C = new TreeNode('C', 'C');\n",
    "var D = new TreeNode('D', 'D');\n",
    "var E = new TreeNode('E', 'E');\n",
    "var F = new TreeNode('F', 'F');\n",
    "\n",
    "r.left = B;\n",
    "r.right = C;\n",
    "B.left = D;\n",
    "D.left = E;\n",
    "E.left = F;\n",
    "\n",
    "console.log(isBalanced2(r));\n",
    "\n",
    "var rr = new TreeNode(1,1);\n",
    "var bb = new TreeNode(2,2);\n",
    "var cc = new TreeNode(3,3);\n",
    "\n",
    "rr.left = bb;\n",
    "rr.right = cc;\n",
    "\n",
    "console.log(isBalanced2(rr));"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## 4.5 Validate BST"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 67,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "3\n",
      "6\n",
      "7\n",
      "8\n",
      "11\n",
      "10\n",
      "12\n",
      "14\n"
     ]
    }
   ],
   "source": [
    "function validBST(node, min = Number.MIN_VALUE, max) {\n",
    "    if(node !== null) {\n",
    "        \n",
    "    }\n",
    "}\n",
    "\n",
    "var r = new TreeNode(10, 10);\n",
    "var B = new TreeNode(7, 7);\n",
    "var C = new TreeNode(12, 12);\n",
    "var D = new TreeNode(6, 6);\n",
    "var E = new TreeNode(3, 3);\n",
    "var F = new TreeNode(8, 8);\n",
    "var G = new TreeNode(11, 11);\n",
    "var H = new TreeNode(14, 14);\n",
    "\n",
    "r.left = B;\n",
    "r.right = C;\n",
    "B.left = D;\n",
    "B.right = F;\n",
    "D.left = E;\n",
    "F.right = G;\n",
    "C.right = H;\n",
    "\n",
    "validBST(r);\n",
    "inOrder(r);"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Book Solutions:\n",
    "* able to be implemented in 2 different ways:\n",
    "    1. using inOrder traversal\n",
    "    2. second build off of bst property where left <= current < right\n",
    "* solution 1:\n",
    "    1. do an inorder traversal\n",
    "    2. while we traverse, we copy elements to an array\n",
    "    3. check if array is sorted. if it is, then we know that it is a bst\n",
    "    - only problem with this is that if there are duplicates, it won't be able to tell if it is a proper bst or not.\n",
    "    - the left one is correct while the right is invalid\n",
    "    - without duplicates, this solution works!\n",
    "* solution 2:\n",
    "    1. start with a range of min = NULL, and max = NULL\n",
    "    2. if we go left, we check that the nodes are within the range min = NULL, and max = root.payload\n",
    "    3. when we go right, we check that the nodes are within the range min = 20, max = NULL\n",
    "    4. branching left updates the max\n",
    "    5. branching right updates the min\n",
    "    6. anything that is out of the ordinary gets updated and returned as false for isBST\n",
    "* Analysis:\n",
    "    - time complexity is O(n) b/c we travel to every node in the graph\n",
    "    - due to using recursion, the space complexity is O(log n) where log n = height of the tree. this is b/c we always travel down a branch then return once we've hit the bottom of the tree.\n",
    "    - going back up the tree removes functions from the stack since we've returned from them and we only push new functions to the stack if they are a new node we haven't fully discovered yet."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 60,
   "metadata": {},
   "outputs": [],
   "source": [
    "//    20         20\n",
    "//   /      vs.    \\\n",
    "// 20              20\n",
    "\n",
    "// solution 1\n",
    "var index = 0;\n",
    "\n",
    "function copyBST(node, array) {\n",
    "    if(root == null) { return; }\n",
    "    copyBST(root.left, array);\n",
    "    array[index] = root.payload;\n",
    "    index++;\n",
    "    copyBST(root.right, array);\n",
    "}\n",
    "\n",
    "function checkBST(root) {\n",
    "    let array = [];\n",
    "    copyBST(root, array);\n",
    "    for(let i = 1; i < array.length; i++) {\n",
    "        if(aray[i] <= array[i - 1]) {\n",
    "            return false;\n",
    "        }\n",
    "    }\n",
    "    return true;\n",
    "}"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 87,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "false\n"
     ]
    }
   ],
   "source": [
    "// solution 2\n",
    "\n",
    "function checkBST(n) {\n",
    "    return _checkBST(n, null, null);\n",
    "}\n",
    "\n",
    "function _checkBST(n, min, max) {\n",
    "    if(n == null) { return true; }\n",
    "    \n",
    "    // if the node's value falls outside of the current range, return false;\n",
    "    if( (min !== null && n.payload <= min) || (max !== null && n.payload > max) ) {\n",
    "        return false;\n",
    "    }\n",
    "    \n",
    "    // check left and right subtrees and narrow down the range as you go\n",
    "    // left range = previous min and current node's data\n",
    "    // right range = current node's data and previous max\n",
    "    if(!_checkBST(n.left, min, n.payload) || !_checkBST(n.right, n.payload, max)) {\n",
    "        return false;\n",
    "    }\n",
    "    return true;\n",
    "}\n",
    "\n",
    "var r = new TreeNode(10, 10);\n",
    "var B = new TreeNode(7, 7);\n",
    "var C = new TreeNode(12, 12);\n",
    "var D = new TreeNode(6, 6);\n",
    "var E = new TreeNode(3, 3);\n",
    "var F = new TreeNode(8, 8);\n",
    "var G = new TreeNode(11, 11);\n",
    "var H = new TreeNode(14, 14);\n",
    "\n",
    "\n",
    "r.left = B;\n",
    "r.right = C;\n",
    "B.left = D;\n",
    "B.right = F;\n",
    "D.left = E;\n",
    "F.right = G;\n",
    "C.right = H;\n",
    "\n",
    "console.log(checkBST(r));"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## 4.6 Successor"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 89,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "16\n",
      "15\n",
      "13\n",
      "10\n",
      "null\n"
     ]
    }
   ],
   "source": [
    "function findMin(node) {\n",
    "    while(node.left !== null) {\n",
    "        node = node.left;\n",
    "    }\n",
    "    return node;\n",
    "}\n",
    "\n",
    "function successor(node) {\n",
    "    if(node === null) { return; }\n",
    "    let succ;\n",
    "    if(node.hasRightChild()) {\n",
    "        succ = findMin(node.right);\n",
    "    }\n",
    "    else {\n",
    "        let x = node;\n",
    "        while(x !== null && x.parent !== null) {\n",
    "            if(x.isLeftChild()) {\n",
    "                succ = x.parent;\n",
    "                break;\n",
    "            }\n",
    "            x = x.parent;\n",
    "        }\n",
    "    }\n",
    "    return succ ? succ.key : null;\n",
    "}\n",
    "\n",
    "var r = new TreeNode(15, 15);\n",
    "var B = new TreeNode(10, 10);\n",
    "var C = new TreeNode(11, 11);\n",
    "var D = new TreeNode(12, 12);\n",
    "var E = new TreeNode(13, 13);\n",
    "var F = new TreeNode(16, 16);\n",
    "var G = new TreeNode(17, 17);\n",
    "var H = new TreeNode(18, 18);\n",
    "\n",
    "r.left = B;\n",
    "r.right = F;\n",
    "B.parent = r;\n",
    "F.parent = r;\n",
    "B.left = C;\n",
    "B.right = D;\n",
    "C.parent = B;\n",
    "D.parent = B;\n",
    "D.right = E;\n",
    "E.parent = D;\n",
    "F.right = G;\n",
    "G.parent = F;\n",
    "G.right = H;\n",
    "H.parent = G;\n",
    "\n",
    "// inOrder = 11, 10, 12, 13, 15, 16, 17, 18\n",
    "console.log(successor(r)); // 15, succ = 16\n",
    "console.log(successor(E)); // 13, succ = 15\n",
    "console.log(successor(D)); //12, succ = 13\n",
    "console.log(successor(C)); // 11, succ 10\n",
    "console.log(successor(H));"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Book Solutions:\n",
    "* exactly the same as our implementation"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## 4.7 Build Order"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 38,
   "metadata": {},
   "outputs": [],
   "source": [
    "class DFSGraph extends Graph {\n",
    "    \n",
    "    constructor() {\n",
    "        super();\n",
    "        this.time = 0;\n",
    "        this.topSortArr = [];\n",
    "    }\n",
    "    \n",
    "    topSort() {\n",
    "        this.dfs();\n",
    "        return this.topSortArr;\n",
    "    }\n",
    "    \n",
    "    dfs() {\n",
    "        for(let [key, vertex] of this.vertList) {\n",
    "            vertex.color = 'white';\n",
    "        }\n",
    "        for(let [key, vertex] of this.vertList) {\n",
    "            if(vertex.color === 'white') {\n",
    "                this.dfsvisit(vertex);\n",
    "            }\n",
    "        }\n",
    "    }\n",
    "    \n",
    "    dfsvisit(startVertex) {\n",
    "        startVertex.color = 'gray';\n",
    "        this.time++;\n",
    "        startVertex.disc = this.time;\n",
    "        \n",
    "        for(let [nbr, weight] of startVertex.getConnections()) {\n",
    "            if(nbr.color === 'white') {\n",
    "                nbr.color = 'gray';\n",
    "                nbr.pred = startVertex;\n",
    "                this.dfsvisit(nbr);\n",
    "            }\n",
    "        }\n",
    "        startVertex.color = 'black';\n",
    "        this.time++;\n",
    "        startVertex.fin = this.time;\n",
    "        this.topSortArr.unshift(startVertex);\n",
    "    }\n",
    "}"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 56,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "f\n",
      "e\n",
      "b\n",
      "a\n",
      "d\n",
      "c\n"
     ]
    }
   ],
   "source": [
    "var g = new DFSGraph();\n",
    "g.addVertex('a');\n",
    "g.addVertex('b');\n",
    "g.addVertex('c');\n",
    "g.addVertex('d');\n",
    "g.addVertex('e');\n",
    "g.addVertex('f');\n",
    "\n",
    "g.addEdge('a', 'd');\n",
    "g.addEdge('f', 'b');\n",
    "g.addEdge('b', 'd');\n",
    "g.addEdge('f', 'a');\n",
    "g.addEdge('d', 'c');\n",
    "\n",
    "g.topSort().forEach(item => console.log(item.id))"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Book Solutions:\n",
    "* basically topological sort\n",
    "* Analysis:\n",
    "    - since topological sort just requires you to modify dfs a little bit, it is O(V + E)\n",
    "    - space = O(V) b/c we need to return the build order"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": []
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## 4.8 First Common Ancestor"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 72,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "5\n"
     ]
    }
   ],
   "source": [
    "var g = new DFSGraph();\n",
    "g.addVertex(1);\n",
    "g.addVertex(2);\n",
    "g.addVertex(3);\n",
    "g.addVertex(5);\n",
    "g.addVertex(6);\n",
    "g.addVertex(7);\n",
    "g.addVertex(12);\n",
    "g.addVertex(13);\n",
    "\n",
    "g.addEdge(1, 2);\n",
    "g.addEdge(2, 3);\n",
    "g.addEdge(2, 5);\n",
    "g.addEdge(5, 6);\n",
    "g.addEdge(6, 7);\n",
    "g.addEdge(1, 12);\n",
    "g.addEdge(12, 13);\n",
    "\n",
    "g.dfs();\n",
    "function FCA(node1, node2, g) {\n",
    "    let minDiscovery = Math.min(node1.disc, node2.disc);\n",
    "    let maxFinish = Math.max(node1.fin, node2.fin);\n",
    "    let ancestor;\n",
    "    for(let [key, vertex] of g.vertList) {\n",
    "        let {disc, fin} = vertex;\n",
    "        if(disc < minDiscovery && fin > maxFinish) {\n",
    "            ancestor = vertex;\n",
    "        }\n",
    "    }\n",
    "    return ancestor;\n",
    "}\n",
    "\n",
    "var ancestor = FCA(g.getVertex(6), g.getVertex(7), g);\n",
    "console.log(ancestor.id)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Book Solutions:\n",
    "* solution 1: with links to parents\n",
    "    1. find the depths of the 2 nodes (how far they are away from the root)\n",
    "    2. compare how deep they are to each other\n",
    "    3. will move up from the deeper node to match the depth of the shallower node\n",
    "    4. once they are at the same depth, we traverse up both their paths until we reach a common node\n",
    "    5. return that node as the first common ancestor\n",
    "    - essentially the same as the linked list intersection one. the 2 nodes would basically have the same path at the beginning but at some point would diverge into their own paths.\n",
    "    - will take O(d) time where d = depth of the deeper node\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 1,
   "metadata": {},
   "outputs": [],
   "source": [
    "// solution 1\n",
    "\n",
    "// traverses up the nodes' ancestors until they have the same ancestor or\n",
    "// they reach the root\n",
    "function commonAncestor(p, q) {\n",
    "    let delta = depth(p) - depth(q);\n",
    "    let first = delta > 0 ? q : p;\n",
    "    let second = delta > 0 ? p : q;\n",
    "    second = goUpBy(second, Math.abs(delta));\n",
    "    \n",
    "    while(first !== second && first !== null && second !== null) {\n",
    "        first = first.parent;\n",
    "        second = second.parent;\n",
    "    }\n",
    "    return first === null || second === null ? null : first;\n",
    "}\n",
    "\n",
    "// moves up the node until it matches the other node's depth\n",
    "function goUpBy(node, delta) {\n",
    "    while(delta > 0 && node !== null) {\n",
    "        node = node.parent;\n",
    "        delta--;\n",
    "    }\n",
    "    return node;\n",
    "}\n",
    "\n",
    "// finds the depth of the nodes\n",
    "function depth(node) {\n",
    "    let depth = 0;\n",
    "    while(node !== null) {\n",
    "        node = node.parent;\n",
    "        depth++;\n",
    "    }\n",
    "    return depth;\n",
    "}"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## 4.9 BST Sequences"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 158,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "{ arr: [] }\n",
      "{ arr: [] }\n",
      "{ arr: [] }\n",
      "{ arr: [] }\n",
      "{ arr: [] }\n"
     ]
    }
   ],
   "source": [
    "var two = new TreeNode(2,2);\n",
    "var one = new TreeNode(1,1);\n",
    "var three = new TreeNode(3,3);\n",
    "var four = new TreeNode(4,4);\n",
    "var five = new TreeNode(5,5);\n",
    "\n",
    "two.left = one;\n",
    "two.right = three;\n",
    "three.left = four;\n",
    "three.right = five;\n",
    "\n",
    "// O(n) preprocessing\n",
    "function createArrays(start) {\n",
    "    let q = new Queue();\n",
    "    let levels = {};\n",
    "    q.enqueue(start);\n",
    "    start.distance = 0;\n",
    "    \n",
    "    while(!q.isEmpty()) {\n",
    "        let current = q.dequeue();\n",
    "        let {distance} = current;\n",
    "        if(levels[distance] === undefined) {\n",
    "            levels[distance] = [];\n",
    "        }\n",
    "        levels[distance].push(current.payload);\n",
    "        if(current.left !== null) {\n",
    "            current.left.distance = distance + 1;\n",
    "            q.enqueue(current.left);\n",
    "        }\n",
    "        if(current.right !== null) {\n",
    "            current.right.distance = distance + 1;\n",
    "            q.enqueue(current.right);\n",
    "        }\n",
    "    }\n",
    "    return levels;\n",
    "}\n",
    "\n",
    "function sequences(levelNodes) {\n",
    "    for(let nodes in levelNodes) {\n",
    "        let arr = [];\n",
    "        let depthNodes = levelNodes[nodes];\n",
    "        depthNodes.forEach((node, i) => {\n",
    "            let arr = [];\n",
    "            arr.concat(depthNodes.slice(0, i));\n",
    "            arr.concat(node);\n",
    "            arr.concat(depthNodes.slice(i+1));\n",
    "            console.log({arr});\n",
    "        })\n",
    "    }\n",
    "} \n",
    "\n",
    "var levels = createArrays(two);\n",
    "sequences(levels);"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Book Solutions:\n",
    "* the root must always be the first element\n",
    "* the order of insertion of the left or right subtrees does not matter\n",
    "* the implementation details are essentially similar to mine where we have to get all the nodes and weave them together"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 2,
   "metadata": {},
   "outputs": [],
   "source": [
    "class bstSequences {\n",
    "    constructor() {\n",
    "        this.sequences = [];\n",
    "    }\n",
    "    \n",
    "    recurse(nodes, travelled) {\n",
    "        let noChild = true;\n",
    "        nodes.forEach(node => {\n",
    "            if(node.left !== null && travelled[node.left.payload] === undefined) {\n",
    "                noChild = false;\n",
    "                travelled[node.left.payload] = true;\n",
    "                this.recurse(nodes.concat([node.left]), travelled);\n",
    "                delete travelled[node.left.value];\n",
    "            }\n",
    "            if(node.right !== null && travelled[node.right.payload] === undefined) {\n",
    "                noChild = false;\n",
    "                travelled[node.right.value] = true;\n",
    "                this.recurse(nodes.concat([node.right]), travelled);\n",
    "                delete travelled[node.right.payload];\n",
    "            }\n",
    "        });\n",
    "        if(noChild) {\n",
    "            this.sequences.push(nodes.map(node => node.payload));\n",
    "        }\n",
    "    }\n",
    "    \n",
    "    bstSeq(bst) {\n",
    "        let startTravelled = {};\n",
    "        startTravelled[bst.value] = true;\n",
    "        this.recurse([bst], startTravelled);\n",
    "        return this.sequences;\n",
    "    }\n",
    "    \n",
    "}"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## 4.10 Check Subtree"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 194,
   "metadata": {},
   "outputs": [],
   "source": [
    "class CheckSubTree{\n",
    "    constructor() {\n",
    "        this.found = false;\n",
    "        this.subtree = false;\n",
    "    }\n",
    "    \n",
    "    checkSub(T1, T2) {\n",
    "        let found = this.findNode(T1, T2.key);\n",
    "        if(found) {\n",
    "            this.preOrderCheck(found, T2);\n",
    "        }\n",
    "        return this.subtree;\n",
    "    }\n",
    "    \n",
    "    findNode(node, key) {\n",
    "        this.findNodeHelper(node, key);\n",
    "        return this.found;\n",
    "    }\n",
    "    \n",
    "    findNodeHelper(node, key) {\n",
    "        if(node !== null) {\n",
    "            if(node.key === key) {\n",
    "                this.found = node;\n",
    "            }\n",
    "            this.findNodeHelper(node.left, key);\n",
    "            this.findNodeHelper(node.right, key)\n",
    "        }\n",
    "    }\n",
    "    \n",
    "    preOrderCheck(T1, T2) {\n",
    "        if(T1 !== null && T2 !== null) {\n",
    "            console.log(T1.key, T2.key)\n",
    "            if(T1.key === T2.key) {\n",
    "                this.subtree = true;\n",
    "            }\n",
    "            this.preOrderCheck(T1.left, T2.left);\n",
    "            this.preOrderCheck(T1.right, T2.right);\n",
    "        }\n",
    "    }\n",
    "}"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 195,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "7 7\n",
      "8 8\n",
      "9 9\n",
      "10 10\n",
      "11 11\n"
     ]
    },
    {
     "data": {
      "text/plain": [
       "true"
      ]
     },
     "execution_count": 195,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "//tree node has key, payload, left, right, and parent\n",
    "\n",
    "// T1\n",
    "var tr = new TreeNode(1,1);\n",
    "var tr2 = new TreeNode(2,2);\n",
    "var tr3 = new TreeNode(3,3);\n",
    "var tr4 = new TreeNode(4,4);\n",
    "var tr5 = new TreeNode(5,5);\n",
    "var tr6 = new TreeNode(6,6);\n",
    "var tr7 = new TreeNode(7,7);\n",
    "var tr8 = new TreeNode(8,8);\n",
    "var tr9 = new TreeNode(9,9);\n",
    "var tr10 = new TreeNode(10,10);\n",
    "var tr11 = new TreeNode(11,11);\n",
    "\n",
    "// T1 connections\n",
    "tr.left = tr2;\n",
    "tr.right = tr3;\n",
    "\n",
    "tr3.left = tr4;\n",
    "tr3.right = tr5;\n",
    "\n",
    "tr5.left = tr6;\n",
    "tr5.right = tr7;\n",
    "\n",
    "tr7.left = tr8;\n",
    "tr7.right = tr9;\n",
    "\n",
    "tr9.left = tr10;\n",
    "tr9.right = tr11;\n",
    "\n",
    "\n",
    "// T2\n",
    "var r7 = new TreeNode(7,7);\n",
    "var r8 = new TreeNode(8,8);\n",
    "var r9 = new TreeNode(9,9);\n",
    "var r10 = new TreeNode(10,10);\n",
    "var r11 = new TreeNode(11,11);\n",
    "\n",
    "// T2 connections\n",
    "r7.left = r8;\n",
    "r7.right = r9;\n",
    "r9.left = r10;\n",
    "r9.right = r11;\n",
    "\n",
    "\n",
    "var checker = new CheckSubTree();\n",
    "checker.checkSub(tr, r7);"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Book Solutions:\n",
    "* solution:\n",
    "    1. search through the larger tree, T1 for any instance of the root of T2\n",
    "    2. once we have found a match, we then call another function that checks whether the 2 subtrees are identical\n",
    "    3. if they are not, find another instance of T2 in T1\n",
    "    4. if there are no instances, still return true b/c __the empty tree is ALWAYS a subtree__\n",
    "* this solution is more complete than mine b/c it will only find 1 instance of the root in the tree. in the case where there are multiple instances, it will fail.\n",
    "* Analysis:\n",
    "    - space complexity = O(log n + log m) b/c it will at most have log n or log m functions in the stack. this is due to the fact that it is only traversing down to the bottom of the tree and then returning from it\n",
    "    - time complexity = O(n + km), where n = number of nodes in the larger tree (T1), m = number of nodes in the smaller tree (T2), and k = number of instances of T2's root in T1.\n",
    "        - this is b/c we would at most be looking at every node in T1 for the root of T2. and for every instance, k, of T2's root, we call another function that would compare every node in T2 to that subtree in T1\n",
    "        - however, that function might not look at every node in T2 b/c it ends right when there is a mismatch"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 3,
   "metadata": {},
   "outputs": [],
   "source": [
    "function containsTree(t1, t2) {\n",
    "    if(t2 == null) { return true; } // empty tree is always a subtree. this is also true for arrays and strings as well\n",
    "    return subTree(t1, t2);\n",
    "}\n",
    "\n",
    "function subTree(r1, r2) {\n",
    "    if(r1 == null) {\n",
    "        return false; //big tree empty and subtree still not found\n",
    "    }\n",
    "    // if we found a match, see if their subtrees match up\n",
    "    else if (r1.payload === r2.payload && matchTree(r1, r2)) {\n",
    "        return true;\n",
    "    }\n",
    "    // traverses through the bigger tree to look for the instance of the root of second tree\n",
    "    return subTree(r1.left, r2) || subTree(r1.right, r2);\n",
    "}\n",
    "\n",
    "function matchTree(r1, r2) {\n",
    "    if(r1 == null && r2 == null) {\n",
    "        return true; // if everything has been checked in the subtree, return true;\n",
    "    }\n",
    "    else if (r1 == null || r2 == null) {\n",
    "        return false; //if either of the trees are empty, it cannot match cause one of them still has more nodes to go\n",
    "    }\n",
    "    else if (r1.payload !== r2.payload) {\n",
    "        return false; // if there are different values at the same position, then they do not match\n",
    "    }\n",
    "    else {\n",
    "        // checks the left and right subtrees\n",
    "        return matchTree(r1.left, r2.left) && matchTree(r1.right, r2.right);\n",
    "    }\n",
    "}"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## 4.11 Random Node"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 529,
   "metadata": {},
   "outputs": [],
   "source": [
    "class BSTNode {\n",
    "    constructor(key, payload, left = null, right = null, parent = null) {\n",
    "        this.key = key;\n",
    "        this.payload = payload;\n",
    "        this.left = left;\n",
    "        this.right = right;\n",
    "        this.parent = parent;\n",
    "        this.leftUnder = 0;\n",
    "        this.rightUnder = 0;\n",
    "    }\n",
    "    \n",
    "    isLeaf() {\n",
    "        return this.left === null && this.right === null;\n",
    "    }\n",
    "    \n",
    "    get totalUnder() {\n",
    "        return this.leftUnder + this.rightUnder;\n",
    "    }\n",
    "}\n",
    "\n",
    "class RandomBST {\n",
    "    constructor() {\n",
    "        this.root = null;\n",
    "    }\n",
    "    \n",
    "    //each time you go down a parent node,\n",
    "    // you are going to be incrementing its nodesUnder property\n",
    "    // which will tell you how many nodes are its subtrees\n",
    "    insert(key, value) {\n",
    "        const newNode = new BSTNode(key, value);\n",
    "        \n",
    "        if(this.root === null) {\n",
    "            this.root = newNode;\n",
    "        }\n",
    "        else {\n",
    "            this._insert(newNode, this.root)\n",
    "        }\n",
    "    }\n",
    "    \n",
    "    _insert(newNode, currentNode) {\n",
    "        if(newNode.key < currentNode.key) {\n",
    "            currentNode.leftUnder++;\n",
    "            if(currentNode.left === null) {\n",
    "                currentNode.left = newNode;\n",
    "                newNode.parent = currentNode;\n",
    "            }\n",
    "            else {\n",
    "                this._insert(newNode, currentNode.left);\n",
    "            }\n",
    "        }\n",
    "        else {\n",
    "            currentNode.rightUnder++;\n",
    "            if(currentNode.right === null) {\n",
    "                currentNode.right = newNode;\n",
    "                newNode.parent = currentNode;\n",
    "            }\n",
    "            else {\n",
    "                this._insert(newNode, currentNode.right);\n",
    "            }\n",
    "        }\n",
    "    }\n",
    "    \n",
    "    find(key) {\n",
    "        if(this.root === null) { return; }\n",
    "        return this._find(this.root, key);\n",
    "    }\n",
    "    \n",
    "    _find(node, key) {\n",
    "        if(node === null) {\n",
    "            return undefined;\n",
    "        }\n",
    "        else if (node.key === key) {\n",
    "            return node;\n",
    "        }\n",
    "        else if (node.key < key) {\n",
    "            return this._find(node.left, key);\n",
    "        }\n",
    "        else if (node.key > key) {\n",
    "            return this._find(node.right, key);\n",
    "        }\n",
    "    }\n",
    "    \n",
    "    delete() {\n",
    "        //delete\n",
    "    }\n",
    "    \n",
    "    getRandomNode() {\n",
    "        if(this.root === null) { return 'root' }\n",
    "        return this._getRandomNode(this.root);\n",
    "    }\n",
    "    \n",
    "    _getRandomNode(node) {\n",
    "        // randNum from 1 - node.totalUnder inclusive\n",
    "//         let randNum = Math.floor(Math.random() * (node.totalUnder + 1)) + 1;\n",
    "        let randNum = Math.random();\n",
    "        let convertedRand = Math.floor(randNum * (node.totalUnder + 1)) + 1;\n",
    "        let leftNodes = (node.leftUnder / node.totalUnder);\n",
    "        if(convertedRand === 1) {\n",
    "            return node;\n",
    "        }\n",
    "        else if (randNum <= leftNodes) {\n",
    "            if(node.left === null) {\n",
    "                return node;\n",
    "            }\n",
    "            return this._getRandomNode(node.left);\n",
    "        }\n",
    "        else {\n",
    "            if(node.right === null) {\n",
    "                return node;\n",
    "            }\n",
    "            return this._getRandomNode(node.right);\n",
    "        }\n",
    "    }\n",
    "}"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 530,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "15\n"
     ]
    }
   ],
   "source": [
    "var g = new RandomBST();\n",
    "var arr = [50, 25, 70, 12, 37, 60, 80, 8, 10, 30, 40, 55, 65, 75, 85];\n",
    "console.log(arr.length)\n",
    "arr.forEach(el => g.insert(el, el));"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 532,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "{ instances: \n",
      "   { '8': 5182,\n",
      "     '10': 5159,\n",
      "     '12': 5113,\n",
      "     '25': 6261,\n",
      "     '30': 3556,\n",
      "     '37': 7308,\n",
      "     '40': 10637,\n",
      "     '50': 6717,\n",
      "     '55': 3012,\n",
      "     '60': 6082,\n",
      "     '65': 8964,\n",
      "     '70': 6998,\n",
      "     '75': 4081,\n",
      "     '80': 8329,\n",
      "     '85': 12601 },\n",
      "  amt: 15 }\n"
     ]
    }
   ],
   "source": [
    "var instances = {};\n",
    "[...new Array(100000)].forEach(item => {\n",
    "    let key = g.getRandomNode().key;\n",
    "    if(instances[key] === undefined) {\n",
    "        instances[key] = 1;\n",
    "    }\n",
    "    else {\n",
    "        instances[key]++;\n",
    "    }\n",
    "})\n",
    "\n",
    "console.log({instances, amt: Object.keys(instances).length})"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Book Solutions:\n",
    "* solution 1: essentially similar to my algorithm\n",
    "    1. as you insert a node into the tree, you keep track of the number of nodes in that node's subtree\n",
    "    2. in get random node, you get a random node, then you see if that number is less than the left node's subtree\n",
    "        - if it is, then go left\n",
    "        - if it is equal, then return that node\n",
    "        - else, go right\n",
    "* Analysis:\n",
    "    - in a balanced tree, this will be O(log n) b/c it will at most be traversing down the tree from the root to a leaf. and the height of the tree = logn\n",
    "    - space complexity would also be O(log n) for the same reason above b/c we would at most have logn function calls in the stack"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 4,
   "metadata": {},
   "outputs": [],
   "source": [
    "class BSTNode2 {\n",
    "    constructor(key, payload, left = null, right = null, parent = null) {\n",
    "        this.key = key;\n",
    "        this.payload = payload;\n",
    "        this.left = left;\n",
    "        this.right = right;\n",
    "        this.parent = parent;\n",
    "        this.leftUnder = 0;\n",
    "        this.rightUnder = 0;\n",
    "    }\n",
    "    \n",
    "    isLeaf() {\n",
    "        return this.left === null && this.right === null;\n",
    "    }\n",
    "    \n",
    "    get totalUnder() {\n",
    "        return this.leftUnder + this.rightUnder;\n",
    "    }\n",
    "}\n",
    "\n",
    "class RandomBST2 {\n",
    "    constructor() {\n",
    "        this.root = null;\n",
    "    }\n",
    "    \n",
    "    //each time you go down a parent node,\n",
    "    // you are going to be incrementing its nodesUnder property\n",
    "    // which will tell you how many nodes are its subtrees\n",
    "    insert(key, value) {\n",
    "        const newNode = new BSTNode2(key, value);\n",
    "        \n",
    "        if(this.root === null) {\n",
    "            this.root = newNode;\n",
    "        }\n",
    "        else {\n",
    "            this._insert(newNode, this.root)\n",
    "        }\n",
    "    }\n",
    "    \n",
    "    _insert(newNode, currentNode) {\n",
    "        if(newNode.key < currentNode.key) {\n",
    "            currentNode.leftUnder++;\n",
    "            if(currentNode.left === null) {\n",
    "                currentNode.left = newNode;\n",
    "                newNode.parent = currentNode;\n",
    "            }\n",
    "            else {\n",
    "                this._insert(newNode, currentNode.left);\n",
    "            }\n",
    "        }\n",
    "        else {\n",
    "            currentNode.rightUnder++;\n",
    "            if(currentNode.right === null) {\n",
    "                currentNode.right = newNode;\n",
    "                newNode.parent = currentNode;\n",
    "            }\n",
    "            else {\n",
    "                this._insert(newNode, currentNode.right);\n",
    "            }\n",
    "        }\n",
    "    }\n",
    "    \n",
    "    find(key) {\n",
    "        if(this.root === null) { return; }\n",
    "        return this._find(this.root, key);\n",
    "    }\n",
    "    \n",
    "    _find(node, key) {\n",
    "        if(node === null) {\n",
    "            return undefined;\n",
    "        }\n",
    "        else if (node.key === key) {\n",
    "            return node;\n",
    "        }\n",
    "        else if (node.key < key) {\n",
    "            return this._find(node.left, key);\n",
    "        }\n",
    "        else if (node.key > key) {\n",
    "            return this._find(node.right, key);\n",
    "        }\n",
    "    }\n",
    "    \n",
    "    getRandomNode() {\n",
    "        if(this.root === null) { return 'root' }\n",
    "        return this._getRandomNode(this.root);\n",
    "    }\n",
    "    \n",
    "    _getRandomNode(node) {\n",
    "        let leftSize = node.left == null ? 0 : left.totalUnder;\n",
    "        let randNum = Math.random();\n",
    "        if(randNum < leftSize) {\n",
    "            return this._getRandomNode(node.left);\n",
    "        }\n",
    "        else if (randNum === left.totalUnder) {\n",
    "            return node;\n",
    "        }\n",
    "        else {\n",
    "            return this._getRandomNode(node.right);\n",
    "        }\n",
    "    }\n",
    "}"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## 4.12 Paths with Sum"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 53,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "4"
      ]
     },
     "execution_count": 53,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "var p1 = new TreeNode(1,1);\n",
    "var p2 = new TreeNode(2,2);\n",
    "var p3 = new TreeNode(3,3);\n",
    "var p5 = new TreeNode(5,5);\n",
    "var p7 = new TreeNode(7,7);\n",
    "var p8 = new TreeNode(8,8);\n",
    "var p9 = new TreeNode(9,9);\n",
    "\n",
    "p1.left = p2;\n",
    "p1.right = p3;\n",
    "p2.parent = p1;\n",
    "p3.parent = p1;\n",
    "\n",
    "p2.left = p8;\n",
    "p2.right = p9;\n",
    "p8.parent = p2;\n",
    "p9.parent = p2;\n",
    "\n",
    "p3.left = p5;\n",
    "p3.right = p7;\n",
    "p5.parent = p3;\n",
    "p7.parent = p3;\n",
    "\n",
    "var pnodes = [p1, p2, p3, p5, p7, p8, p9]\n",
    "\n",
    "function pathSums(sum, start, nodes) {\n",
    "    let total = 0;\n",
    "    nodes.forEach(node => {\n",
    "        total = _pathSums(total, sum, node);\n",
    "    })\n",
    "    return total;\n",
    "}\n",
    "\n",
    "function _pathSums(total, sum, node) {\n",
    "    if(node !== null) {\n",
    "        if(node.runningSum == null) {\n",
    "            node.runningSum = node.payload;\n",
    "        }\n",
    "        if(node.parent !== null) {\n",
    "            node.runningSum = node.parent.runningSum + node.payload;\n",
    "        }\n",
    "        if(node.runningSum === sum || (node.parent !== null && node.payload + node.parent.runningSum === sum)) {\n",
    "            total++;\n",
    "        }\n",
    "        return _pathSums(total, sum, node.left);\n",
    "        return _pathSums(total, sum, node.right);\n",
    "    }\n",
    "    else {\n",
    "        return total;\n",
    "    }\n",
    "}\n",
    "\n",
    "pathSums(11, p1, pnodes);"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Book Solutions:\n",
    "* solution:\n",
    "    1. visiting each node, track runningSum by incrementing it with node.payload\n",
    "    2. look up runningSum - targetSum in hash table and set up totalPaths = that value\n",
    "    3. if runningSum == targetSum, increment totalPaths\n",
    "    4. add runningSum to hash table (inc if it's already there)\n",
    "    5. recurse left and right, counting number of paths with sum targetSum\n",
    "    6. after recursing, decrement value of runningSum in hash table\n",
    "        - reverses changes to hash table so that other nodes don't use it!\n",
    "    - __THE REASON WHY WE USE THE HASH TABLE IS B/C IT KEEPS TRACK OF THE SUMS THAT WE HAVE SEEN PREVIOUSLY THAT DO NOT START AT THE ROOT. SO IF THE CURRENT NODE'S VALUE - TARGETSUM = ANY SUM WE HAVE SEEN ON THE PATH FROM THE ROOT TO THE CURRENT NODE, THEN WE KNOW THAT WE HAVE A PATH FOR THE TARGETSUM\n",
    "* Analysis:\n",
    "    - time complexity = O(n) b/c we visit every node in the tree once doing O(1) work with the hash table\n",
    "    - space complexity = O(log n) for a balanced tree but can bloat to O(n) for an unbalanced tree"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 24,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "{ runningSum: 1, sum: -10, totalPaths: 0 }\n",
      "{ runningSum: 3, sum: -8, totalPaths: 0 }\n",
      "{ runningSum: 11, sum: 0, totalPaths: 0 }\n",
      "{ results: 1 }\n",
      "{ runningSum: 12, sum: 1, totalPaths: 1 }\n",
      "{ results: 1 }\n",
      "{ results: 2 }\n",
      "{ runningSum: 4, sum: -7, totalPaths: 0 }\n",
      "{ runningSum: 9, sum: -2, totalPaths: 0 }\n",
      "{ results: 0 }\n",
      "{ runningSum: 11, sum: 0, totalPaths: 0 }\n",
      "{ results: 1 }\n",
      "{ results: 1 }\n",
      "{ results: 3 }\n"
     ]
    },
    {
     "data": {
      "text/plain": [
       "3"
      ]
     },
     "execution_count": 24,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "function countPathsWithSum(root, targetSum) {\n",
    "    let sumTable = {};\n",
    "    return _countPathsWithSum(root, targetSum, 0, sumTable);\n",
    "}\n",
    "\n",
    "function _countPathsWithSum(node, targetSum, runningSum, sumTable) {\n",
    "    if(node == null) { return 0; }\n",
    "    \n",
    "    runningSum += node.payload;\n",
    "    let sum = runningSum - targetSum;\n",
    "//     console.log({runningSum})\n",
    "    \n",
    "    // totalPaths keeps track of any sums we have seen so far on the way that does not start at the root\n",
    "    let totalPaths = sumTable[sum] === undefined ? 0 : sumTable[sum];\n",
    "    console.log({runningSum, sum, totalPaths})\n",
    "    \n",
    "    if(runningSum === targetSum) {\n",
    "        totalPaths++;\n",
    "    }\n",
    "    \n",
    "    // initializes or increments the current runningSum into the hash table and adds it by 1\n",
    "    incrementHashTable(sumTable, runningSum, 1);\n",
    "    \n",
    "    // traverses left and right to check if the the targetSum is in\n",
    "    totalPaths += _countPathsWithSum(node.left, targetSum, runningSum, sumTable);\n",
    "    totalPaths += _countPathsWithSum(node.right, targetSum, runningSum, sumTable);\n",
    "    \n",
    "    // once we have traversed all paths and returned back, we remove the runningSum before so that\n",
    "    // once we branch to other portions of the tree, that particular sum will no longer be used\n",
    "    // this is to prevent errors where we find the sum in the hash table when it is not actually\n",
    "    // in the same path as the current node\n",
    "    incrementHashTable(sumTable, runningSum, -1);\n",
    "    console.log({results: totalPaths})\n",
    "    \n",
    "    return totalPaths;\n",
    "}\n",
    "\n",
    "// literally increments sum in hash table by 1 or -1\n",
    "function incrementHashTable(sumTable, key, delta) {\n",
    "    let sum = sumTable[key] === undefined ? 0 : sumTable[key];\n",
    "    let newCount = sum + delta;\n",
    "    if(newCount === 0) {\n",
    "        delete sumTable[key];\n",
    "    }\n",
    "    else {\n",
    "        sumTable[key] = newCount;\n",
    "    }\n",
    "}\n",
    "\n",
    "var p1 = new TreeNode(1,1);\n",
    "var p2 = new TreeNode(2,2);\n",
    "var p3 = new TreeNode(3,3);\n",
    "var p5 = new TreeNode(5,5);\n",
    "var p7 = new TreeNode(7,7);\n",
    "var p8 = new TreeNode(8,8);\n",
    "var p9 = new TreeNode(9,9);\n",
    "\n",
    "p1.left = p2;\n",
    "p1.right = p3;\n",
    "p2.parent = p1;\n",
    "p3.parent = p1;\n",
    "\n",
    "p2.left = p8;\n",
    "p2.right = p9;\n",
    "p8.parent = p2;\n",
    "p9.parent = p2;\n",
    "\n",
    "p3.left = p5;\n",
    "p3.right = p7;\n",
    "p5.parent = p3;\n",
    "p7.parent = p3;\n",
    "\n",
    "countPathsWithSum(p1, 11);\n",
    "// the runningSums here do not keep getting bigger b/c it returns from the function that added it and the \n",
    "// local variables stay the same as before\n",
    "// that's why we have 11 --> 12 --> 4\n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "# Summary:\n",
    "* __BE VERY COMFORTABLE WITH USING INORDER, PREORDER, AND POSTORDER TRAVERSALS AS WELL AS DFS AND BFS__\n",
    "    - most algorithms for these problems are basically modified versions of them and can make your life way easier\n",
    "    - know exactly when to use them\n",
    "* be very comfortable with using recursion b/c almost every single traversal is recursive\n",
    "    - understand what is going on with the variables in each recursive call.\n",
    "    - do they get passed to each recursive call\n",
    "    - do the variables change their value if they get modified in another recursive call?\n",
    "    - <a href=\"https://stackoverflow.com/questions/39829624/can-a-recursive-function-change-a-variable-in-the-original-calling-of-the-functi\">this link should be able to address these questions in regards to local variables</a>"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": []
  }
 ],
 "metadata": {
  "kernelspec": {
   "display_name": "Javascript (Node.js)",
   "language": "javascript",
   "name": "javascript"
  },
  "language_info": {
   "file_extension": ".js",
   "mimetype": "application/javascript",
   "name": "javascript",
   "version": "13.12.0"
  }
 },
 "nbformat": 4,
 "nbformat_minor": 2
}