Trees.ipynb

{
 "cells": [
  {
   "cell_type": "markdown",
   "id": "0ea9f33d",
   "metadata": {},
   "source": [
    "# Easy"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "e6c8949e",
   "metadata": {},
   "source": [
    "## Invert Binary Tree\n",
    "\n",
    "* https://leetcode.com/problems/invert-binary-tree/\n",
    "***\n",
    "*  Time Complexity: O(n)\n",
    "    - traversing through every node in the tree and reversing its children\n",
    "* Space Complexity: O(1)\n",
    "    - we reverse them in place so no extra memory is used\n",
    "***\n",
    "* use of post-order traversal (Left --> Right --> Root) to get this done\n",
    "    - we want to keep traversing until we hit the leaves and reverse them\n",
    "    - then as we go back up to the root, we finally reverse the subtrees"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 1,
   "id": "33fad4ff",
   "metadata": {},
   "outputs": [],
   "source": [
    "/**\n",
    " * Definition for a binary tree node.\n",
    " * function TreeNode(val, left, right) {\n",
    " *     this.val = (val===undefined ? 0 : val)\n",
    " *     this.left = (left===undefined ? null : left)\n",
    " *     this.right = (right===undefined ? null : right)\n",
    " * }\n",
    " */\n",
    "/**\n",
    " * @param {TreeNode} root\n",
    " * @return {TreeNode}\n",
    " */\n",
    "var invertTree = function(root) {\n",
    "    if (root === null) return root;\n",
    "    \n",
    "    const traverse = (node) => {\n",
    "        if (node !== null) {\n",
    "            traverse(node.left);\n",
    "            traverse(node.right);\n",
    "            [node.left, node.right] = [node.right, node.left];\n",
    "        }\n",
    "    }\n",
    "    \n",
    "    traverse(root);\n",
    "    \n",
    "    return root;\n",
    "};"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "9b74344a",
   "metadata": {},
   "source": [
    "## Maximum Depth of Binary Tree"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 3,
   "id": "bf71d48a",
   "metadata": {},
   "outputs": [],
   "source": [
    "/**\n",
    " * Definition for a binary tree node.\n",
    " * function TreeNode(val, left, right) {\n",
    " *     this.val = (val===undefined ? 0 : val)\n",
    " *     this.left = (left===undefined ? null : left)\n",
    " *     this.right = (right===undefined ? null : right)\n",
    " * }\n",
    " */\n",
    "/**\n",
    " * @param {TreeNode} root\n",
    " * @return {number}\n",
    " */\n",
    "\n",
    "// recursion\n",
    "var maxDepth = function(root) {\n",
    "    if (root === null) return 0;\n",
    "    return 1 + Math.max(maxDepth(root.left), maxDepth(root.right));\n",
    "};\n",
    "\n",
    "var Queue = class {\n",
    "    constructor() {\n",
    "        this.queue = [];\n",
    "    }\n",
    "    \n",
    "    enqueue(item) {\n",
    "        this.queue.push(item);\n",
    "    }\n",
    "    \n",
    "    dequeue() {\n",
    "        const value = this.queue.shift();\n",
    "        return value;\n",
    "    }\n",
    "    \n",
    "    isEmpty() {\n",
    "        return this.queue.length === 0;\n",
    "    }\n",
    "    \n",
    "    get length() {\n",
    "        return this.queue.length;\n",
    "    }\n",
    "    \n",
    "    get items() {\n",
    "        return this.queue;\n",
    "    }\n",
    "}\n",
    "\n",
    "// iterative BFS\n",
    "var maxDepth = function(root) {\n",
    "    if (root === null) return 0;\n",
    "    \n",
    "    const queue = new Queue();\n",
    "    let depth = 0;\n",
    "    queue.enqueue(root);\n",
    "    \n",
    "    while (!queue.isEmpty()) {\n",
    "        const len = queue.length;\n",
    "        for (let i = 0; i < len; i++) {\n",
    "            let node = queue.dequeue();\n",
    "            if (node.left !== null) {\n",
    "                queue.enqueue(node.left);\n",
    "            }\n",
    "            if (node.right !== null) {\n",
    "                queue.enqueue(node.right);\n",
    "            }\n",
    "        }\n",
    "        depth++;\n",
    "    }\n",
    "    \n",
    "    return depth;\n",
    "}\n",
    "\n",
    "// iterative dfs\n",
    "var maxDepth = function(root) {\n",
    "    if (root === null) return 0;\n",
    "    \n",
    "    const stack = [[root, 1]];\n",
    "    let depth = 0;\n",
    "    \n",
    "    while (!(stack.length === 0)) {\n",
    "        let [node, currentDepth] = stack.pop();\n",
    "        if (node.left !== null) {\n",
    "            stack.push([node.left, currentDepth + 1]);\n",
    "        }\n",
    "        if (node.right !== null) {\n",
    "            stack.push([node.right, currentDepth + 1]);\n",
    "        }\n",
    "        depth = Math.max(depth, currentDepth);\n",
    "    }\n",
    "    \n",
    "    return depth;\n",
    "}"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "3cd40577",
   "metadata": {},
   "source": [
    "## Diameter of Binary Tree\n",
    "\n",
    "* https://leetcode.com/problems/diameter-of-binary-tree/\n",
    "***\n",
    "* Time Complexity: O(n)\n",
    "    - basically a post-order traversal\n",
    "    - you vist each node once\n",
    "* Space Complexity: O(1)\n",
    "    - you just keep track of the max with 1 variable\n",
    "***\n",
    "* for these types of problems when you need to figure out the max of something for each node, you can just have a variable, max\n",
    "* and when you need to do something for each node, think of the 3 traversals (pre-order, in-order, and post-order)\n",
    "* if you're doing something bottom-up using the traversals, the usual structure is 1 + Math.max(left subtree, right subtree)\n",
    "    - 1 represents the current node\n",
    "    - and you want the best value from either the left or right subtree"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 1,
   "id": "c6586dda",
   "metadata": {},
   "outputs": [],
   "source": [
    "/**\n",
    " * Definition for a binary tree node.\n",
    " * function TreeNode(val, left, right) {\n",
    " *     this.val = (val===undefined ? 0 : val)\n",
    " *     this.left = (left===undefined ? null : left)\n",
    " *     this.right = (right===undefined ? null : right)\n",
    " * }\n",
    " */\n",
    "/**\n",
    " * @param {TreeNode} root\n",
    " * @return {number}\n",
    " */\n",
    "\n",
    "var diameterOfBinaryTree = function(root) {\n",
    "    let max = 0;\n",
    "    \n",
    "    const traverse = (node) => {\n",
    "        // by convention, empty tree = -1\n",
    "        if (node === null) return 0;\n",
    "        \n",
    "        // post-order traversal\n",
    "        let left = traverse(node.left);\n",
    "        let right = traverse(node.right);\n",
    "        \n",
    "        // store the max in the res variable\n",
    "        max = Math.max(max, left + right);\n",
    "        \n",
    "        // looks at max of left or right subtrees and adds 1 to it\n",
    "        // the 1 represents the root-edge + maxdepth(left) or maxdepth(right), whichever is bigger\n",
    "        return 1 + Math.max(left, right);\n",
    "    }\n",
    "    \n",
    "    traverse(root);\n",
    "    \n",
    "    return max;\n",
    "};"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "91a795e8",
   "metadata": {},
   "source": [
    "## Balanced Binary Tree\n",
    "\n",
    "* https://leetcode.com/problems/balanced-binary-tree/\n",
    "***\n",
    "* Time Complexity: O(n)\n",
    "    - basically a post-order traversal that visits every node in the tree once\n",
    "* Space Complexity: O(1)\n",
    "    - only use a couple of variables\n",
    "***\n",
    "* similar to diameter of a binary tree in that you do a post-order traversal that moves from the bottom up and returns the max height of the left or right subtrees\n",
    "* and as you traverse, you also calculate whether the tree is balanced at all nodes\n",
    "* Structure:\n",
    "    1. base case (node === null) return -1 or 0\n",
    "    2. traverse left\n",
    "    3. traverse right\n",
    "    4. calculations to solve the subproblem, e.g. is the current node we're looking at balanced?\n",
    "        - subproblem used to solve the entire problem.\n",
    "        - if the current node is NOT balanced, we know the entire TREE is not balanced\n",
    "    5. return 1 + Math.max(left, right)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 3,
   "id": "53c50814",
   "metadata": {},
   "outputs": [],
   "source": [
    "/**\n",
    " * Definition for a binary tree node.\n",
    " * function TreeNode(val, left, right) {\n",
    " *     this.val = (val===undefined ? 0 : val)\n",
    " *     this.left = (left===undefined ? null : left)\n",
    " *     this.right = (right===undefined ? null : right)\n",
    " * }\n",
    " */\n",
    "/**\n",
    " * @param {TreeNode} root\n",
    " * @return {boolean}\n",
    " */\n",
    "var isBalanced = function(root) {\n",
    "    if (root === null) return true;\n",
    "    let balanced = true;\n",
    "    \n",
    "    const traverse = (node) => {\n",
    "        if (node === null) return -1;\n",
    "        \n",
    "        let left = traverse(node.left);\n",
    "        let right = traverse(node.right);\n",
    "        \n",
    "        let difference = Math.abs(left - right);\n",
    "        \n",
    "        balanced = balanced && difference < 2;\n",
    "            \n",
    "        return 1 + Math.max(left, right);\n",
    "    }\n",
    "    \n",
    "    traverse(root);\n",
    "    return balanced;\n",
    "};"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "3b630ceb",
   "metadata": {},
   "source": [
    "## Same Tree\n",
    "\n",
    "* https://leetcode.com/problems/same-tree/\n",
    "***\n",
    "* O(p + q)\n",
    "    - p and q represent the # of nodes in each tree\n",
    "    - realistically, it's probably closer to the smaller tree + 1 b/c we know that if both are the same except for 1 extra node in q or something, we'd immediately return from it\n",
    "* O(1)\n",
    "    - no extra memory is used to calculate this\n",
    "    - it would be O(n) though if we did count the stack used for recursion\n",
    "***\n",
    "* basically another tree traversal problem\n",
    "    - in this case, it's pre-order traversal where we check the current node (root) then move onto the left and right subtrees. root --> Left --> Right"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 1,
   "id": "8393ab6f",
   "metadata": {},
   "outputs": [],
   "source": [
    "/**\n",
    " * Definition for a binary tree node.\n",
    " * function TreeNode(val, left, right) {\n",
    " *     this.val = (val===undefined ? 0 : val)\n",
    " *     this.left = (left===undefined ? null : left)\n",
    " *     this.right = (right===undefined ? null : right)\n",
    " * }\n",
    " */\n",
    "/**\n",
    " * @param {TreeNode} p\n",
    " * @param {TreeNode} q\n",
    " * @return {boolean}\n",
    " */\n",
    "var isSameTree = function(p, q) {\n",
    "    const traverse = (node1, node2) => {\n",
    "        if (node1 === null && node2 === null) return true;\n",
    "        if ((node1 === null || node2 === null) || (node1.val !== node2.val)) return false\n",
    "        \n",
    "        return traverse(node1.left, node2.left) && traverse(node1.right, node2.right);\n",
    "    }\n",
    "    \n",
    "    return traverse(p, q);\n",
    "};"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "b861cc82",
   "metadata": {},
   "source": [
    "## Subtree of Another Tree\n",
    "\n",
    "* https://leetcode.com/problems/subtree-of-another-tree/\n",
    "***\n",
    "* Time Complexity: O(r * s)\n",
    "    - r = root tree and s = subroot tree we are trying to find in r\n",
    "    - r * s b/c we'll have to find the root of s in r\n",
    "    - once that's done, we then check if r and s are the same tree by passing it into sameTree\n",
    "* Space Complexity: O(1)\n",
    "    - no extra memory used\n",
    "    - but if we count the function stack used for recursion, it'd probably be O(r + s) since we'd have function calls that actually traverse r to find the root s, then once we find it, we'd have to do s number of function calls to see if it's the same tree"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "id": "06b959e5",
   "metadata": {},
   "outputs": [],
   "source": [
    "/**\n",
    " * Definition for a binary tree node.\n",
    " * function TreeNode(val, left, right) {\n",
    " *     this.val = (val===undefined ? 0 : val)\n",
    " *     this.left = (left===undefined ? null : left)\n",
    " *     this.right = (right===undefined ? null : right)\n",
    " * }\n",
    " */\n",
    "/**\n",
    " * @param {TreeNode} root\n",
    " * @param {TreeNode} subRoot\n",
    " * @return {boolean}\n",
    " */\n",
    "\n",
    "var sameTree = (node1, node2) => {\n",
    "    if (node1 === null && node2 === null) return true;\n",
    "    \n",
    "    if (node1 === null || node2 === null || (node1.val !== node2.val)) return false;\n",
    "    \n",
    "    return sameTree(node1.left, node2.left) && sameTree(node1.right, node2.right);\n",
    "}\n",
    "\n",
    "var isSubtree = function(root, subRoot) {\n",
    "    \n",
    "    const traverse = (node) => {\n",
    "        if (node === null) return false;\n",
    "        \n",
    "        let isSame;\n",
    "        if (node.val === subRoot.val) {\n",
    "            isSame = sameTree(node, subRoot);\n",
    "        }\n",
    "        \n",
    "        if (isSame) return true;\n",
    "        \n",
    "        return traverse(node.left) || traverse(node.right);\n",
    "    }\n",
    "    \n",
    "    return traverse(root);\n",
    "};"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "bc63bf42",
   "metadata": {},
   "source": [
    "## Lowest Common Ancestor of a Binary Search Tree\n",
    "\n",
    "* https://leetcode.com/problems/lowest-common-ancestor-of-a-binary-search-tree/\n",
    "***\n",
    "* Time Complexity: O(log n)\n",
    "    - since we are looking for the LCA in a BINARY SEARCH TREE, we can use this to our advantage to essentially reduce our search size by half.\n",
    "    - the BST property = for every node in the BST, all of the values in its left subtree are smaller than itself (or equal to) and all the values in its right subtree are greater than it\n",
    "    - so if the current node is SMALLER than the smallest value of p and q, we can disregard the current node's left subtree b/c all of the nodes there will ALSO have smaller values than p or q\n",
    "* Space Complexity: O(1)\n",
    "    - no extra data structure is used\n",
    "    - the iterative solution would have O(1)\n",
    "    - the recursive solution, implicitly, would have O(log n) function calls b/c, like the time complexity reasoning, we'd be disregarding half of the input size for every function call and would at most go down the height of the tree which is log n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 2,
   "id": "51730e42",
   "metadata": {},
   "outputs": [],
   "source": [
    "/**\n",
    " * Definition for a binary tree node.\n",
    " * function TreeNode(val) {\n",
    " *     this.val = val;\n",
    " *     this.left = this.right = null;\n",
    " * }\n",
    " */\n",
    "\n",
    "/**\n",
    " * @param {TreeNode} root\n",
    " * @param {TreeNode} p\n",
    " * @param {TreeNode} q\n",
    " * @return {TreeNode}\n",
    " */\n",
    "\n",
    "// recursive solution\n",
    "var lowestCommonAncestor = function(root, p, q) {\n",
    "    let node1;\n",
    "    let node2;\n",
    "    \n",
    "    // identify which one is smaller between p and q\n",
    "    // and assign smallest to node1 and the other to node2\n",
    "    if (p.val < q.val) {\n",
    "        node1 = p;\n",
    "        node2 = q;\n",
    "    }\n",
    "    else {\n",
    "        node1 = q;\n",
    "        node2 = p;\n",
    "    }\n",
    "    \n",
    "    const traverse = (current, node1, node2) => {\n",
    "        // a node is a descendant of itself so this is the LOWEST it can be\n",
    "        if (current.val === node1.val || current.val === node2.val) return current;\n",
    "        \n",
    "        // if the current node is between node1 and node2, then it is the lowest\n",
    "        // reason being, going into the current's left or right subtrees would not\n",
    "        // have the other as a descendant\n",
    "        if (node1.val < current.val && current.val < node2.val) return current;\n",
    "        \n",
    "        // if current is less than the smallest of the 2, then go to the right subtree\n",
    "        // b/c the left subtree will not have them\n",
    "        if (current.val < node1.val) {\n",
    "            return traverse(current.right, node1, node2);\n",
    "        }\n",
    "        \n",
    "        return traverse(current.left, node1, node2);\n",
    "    }\n",
    "    \n",
    "    return traverse(root, node1, node2);\n",
    "};\n",
    "\n",
    "// iterative solution\n",
    "var lowestCommonAncestor = function(root, p, q) {\n",
    "    let node1;\n",
    "    let node2;\n",
    "    \n",
    "    // identify which one is smaller between p and q\n",
    "    // and assign smallest to node1 and the other to node2\n",
    "    if (p.val < q.val) {\n",
    "        node1 = p;\n",
    "        node2 = q;\n",
    "    }\n",
    "    else {\n",
    "        node1 = q;\n",
    "        node2 = p;\n",
    "    }\n",
    "    \n",
    "    let current = root;\n",
    "    \n",
    "    while (current !== null) {\n",
    "        \n",
    "        if (current.val === node1.val || current.val === node2.val) return current;\n",
    "        \n",
    "        if (node1.val < current.val && current.val < node2.val) return current;\n",
    "        \n",
    "        if (current.val < node1.val) {\n",
    "            current = current.right;\n",
    "        }\n",
    "        else {\n",
    "            current = current.left;\n",
    "        }\n",
    "    }\n",
    "};"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "a78728d3",
   "metadata": {},
   "source": [
    "## Convert Sorted Array to Binary Search Tree\n",
    "\n",
    "* https://leetcode.com/problems/convert-sorted-array-to-binary-search-tree/description/\n",
    "***\n",
    "* Time Complexity: O(n)\n",
    "    - have to convert the entire sorted array so must traverse through all elements in the array\n",
    "* Space Complexity: O(logn)\n",
    "    - uses recursion to create the BST so requires some space for functions on the stack\n",
    "    - every recursion splits the array into 2 pieces so the each branch of the tree will only be logn in length\n",
    "***\n",
    "* similar to binary search, we find the midpoint\n",
    "* the difference is that we create the node for the midpoint and recurse on the left and right subarrays\n",
    "    - in this case, we use 2 points, start and end, to optimize for space and save the location of the subarrays\n",
    "    - if start > end, we just return null\n",
    "* i initially messed up my recursion by going from [0...mid - 1] instead of [start...mid - 1]\n",
    "    - start is correct because if we are creating left-side nodes for the right subtree, we want to work on everything to the right of the initial root, not at 0"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 1,
   "id": "761595c5",
   "metadata": {},
   "outputs": [],
   "source": [
    "/**\n",
    " * Definition for a binary tree node.\n",
    " * function TreeNode(val, left, right) {\n",
    " *     this.val = (val===undefined ? 0 : val)\n",
    " *     this.left = (left===undefined ? null : left)\n",
    " *     this.right = (right===undefined ? null : right)\n",
    " * }\n",
    " */\n",
    "/**\n",
    " * @param {number[]} nums\n",
    " * @return {TreeNode}\n",
    " */\n",
    "var sortedArrayToBST = function(nums) {\n",
    "    const n = nums.length;\n",
    "\n",
    "    const traverse = (start, end) => {\n",
    "        if (start > end) return null;\n",
    "        \n",
    "        const mid = Math.trunc(start + ((end - start) / 2));\n",
    "        const newNode = new TreeNode(nums[mid]);\n",
    "\n",
    "        // i messed up and put 0 instead of start\n",
    "        newNode.left = traverse(start, mid - 1);\n",
    "        newNode.right = traverse(mid + 1, end);\n",
    "\n",
    "        return newNode;\n",
    "    }\n",
    "\n",
    "    return traverse(0, n - 1);\n",
    "};"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "c6a0d999",
   "metadata": {},
   "source": [
    "# Medium"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "e47e3220",
   "metadata": {},
   "source": [
    "## Binary Tree Level Order Traversal\n",
    "\n",
    "* https://leetcode.com/problems/binary-tree-level-order-traversal/\n",
    "***\n",
    "* Time Complexity: O(n)\n",
    "    - you visit every node and add its left and right child if it has any\n",
    "* Space Complexity O(n)\n",
    "    - you'll have an array of int. arrs where each int. arr represents the level of the tree and the node values in that level\n",
    "***\n",
    "* it's essentially BFS\n",
    "    - use a queue\n",
    "    - add root to the queue\n",
    "    - pop the root off and add its children into the queue\n",
    "    - do this until the queue is empty\n",
    "    - for the implementation, use a while loop for the queue and a nested for loop for the level\n",
    "        * GET THE CURRENT LENGTH OF THE QUEUE FIRST THEN PUT IT INTO THE FOR LOOP OR ELSE THAT LENGTH GETS UPDATED AS YOU ADD MORE STUFF INTO IT\n",
    "        * BY USING A VARIABLE, THAT LENGTH DOESN'T CHANGE\n",
    "        * for example:\n",
    "            - let qLen = queue.length;\n",
    "            - for (let i = 0; i < qLen; i++);\n",
    "            - DO NOT USE: for (let i = 0; i < queue.length; i++); THIS WILL GET UPDATED"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 1,
   "id": "a8d4b45b",
   "metadata": {},
   "outputs": [],
   "source": [
    "/**\n",
    " * Definition for a binary tree node.\n",
    " * function TreeNode(val, left, right) {\n",
    " *     this.val = (val===undefined ? 0 : val)\n",
    " *     this.left = (left===undefined ? null : left)\n",
    " *     this.right = (right===undefined ? null : right)\n",
    " * }\n",
    " */\n",
    "/**\n",
    " * @param {TreeNode} root\n",
    " * @return {number[][]}\n",
    " */\n",
    "var levelOrder = function(root) {\n",
    "    if (root == null) return [];\n",
    "    \n",
    "    let res = [];\n",
    "    res.push([root]);\n",
    "    let i = 0;\n",
    "    \n",
    "    while (i < res.length) {\n",
    "        let currentLevel = res[i];\n",
    "        for (let j = 0; j < currentLevel.length; j++) {\n",
    "            if (currentLevel[j].left !== null || currentLevel[j].right !== null) {\n",
    "                if (res[i + 1] === undefined) {\n",
    "                    res.push([]);\n",
    "                }\n",
    "                if (currentLevel[j].left !== null) {\n",
    "                    res[i + 1].push(currentLevel[j].left);\n",
    "                }\n",
    "                if (currentLevel[j].right !== null) {\n",
    "                    res[i + 1].push(currentLevel[j].right);\n",
    "                }\n",
    "            }\n",
    "            currentLevel[j] = currentLevel[j].val;\n",
    "        }\n",
    "        i++;\n",
    "    }\n",
    "    return res;\n",
    "};"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "985b00d1",
   "metadata": {},
   "source": [
    "## Binary Tree Right Side View\n",
    "\n",
    "* https://leetcode.com/problems/binary-tree-right-side-view/\n",
    "***\n",
    "* Time Complexity: O(n)\n",
    "    - basically traversing through the entire tree and pushing the rightmost values at every level into res array\n",
    "* Space Complexity: O(n)\n",
    "    - you need a queue to keep track of the levels and you need a res array to store the output\n",
    "***\n",
    "* basically BFS\n",
    "* you add all nodes in a certain level of the tree into the queue and you take the rightmost node in the queue and add it to your res array\n",
    "    - since you're doing this level by level, the rightmost node in the queue is going to be in the same level as the other nodes"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 1,
   "id": "32f5a88d",
   "metadata": {},
   "outputs": [],
   "source": [
    "/**\n",
    " * Definition for a binary tree node.\n",
    " * function TreeNode(val, left, right) {\n",
    " *     this.val = (val===undefined ? 0 : val)\n",
    " *     this.left = (left===undefined ? null : left)\n",
    " *     this.right = (right===undefined ? null : right)\n",
    " * }\n",
    " */\n",
    "/**\n",
    " * @param {TreeNode} root\n",
    " * @return {number[]}\n",
    " */\n",
    "var rightSideView = function(root) {\n",
    "    if (root == null) return [];\n",
    "    \n",
    "    const queue = [root];\n",
    "    let res = [root.val];\n",
    "    \n",
    "    while (queue.length > 0) {\n",
    "        let qLen = queue.length;\n",
    "        for (let i = 0; i < qLen; i++) {\n",
    "            let current = queue.shift();\n",
    "            if (current.left) queue.push(current.left);\n",
    "            if (current.right) queue.push(current.right);\n",
    "        }\n",
    "        if (queue.length > 0) res.push(queue[queue.length - 1].val);\n",
    "    }\n",
    "    \n",
    "    return res;\n",
    "};"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "b5f6e808",
   "metadata": {},
   "source": [
    "## Count Good Nodes in Binary Tree\n",
    "\n",
    "* https://leetcode.com/problems/count-good-nodes-in-binary-tree/\n",
    "***\n",
    "* Time Complexity: O(n)\n",
    "    - have to traverse through all of the nodes to check if they're a good node\n",
    "* Space Complexity: O(height of tree)\n",
    "    - since we're doing a recursive preorder traversal, we also have a function stack which will have function calls, at most, being the height of the tree.\n",
    "    - this traversal goes from the root --> leaf basically and backtracks and since you return from them once a branch is fully visited, you'll never have any more than that in the function stack\n",
    "***\n",
    "* preorder traversal while maintaining a max value so far\n",
    "* we know that the root wil ALWAYS be a good node b/c the tree starts there. there can never be a node that precedes it\n",
    "    - so the max is -infinity\n",
    "    - then for its children, the max value the children have seen so far is the root, etc\n",
    "    - so as you go down the tree, keep track of the max value you've seen so far"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 2,
   "id": "e2d0c4e7",
   "metadata": {},
   "outputs": [],
   "source": [
    "/**\n",
    " * Definition for a binary tree node.\n",
    " * function TreeNode(val, left, right) {\n",
    " *     this.val = (val===undefined ? 0 : val)\n",
    " *     this.left = (left===undefined ? null : left)\n",
    " *     this.right = (right===undefined ? null : right)\n",
    " * }\n",
    " */\n",
    "/**\n",
    " * @param {TreeNode} root\n",
    " * @return {number}\n",
    " */\n",
    "var goodNodes = function(root) {\n",
    "    let numGood = 0;\n",
    "    \n",
    "    const traverse = (node, max) => {\n",
    "        if (node !== null) {\n",
    "            if (max <= node.val) {\n",
    "                max = node.val;\n",
    "                numGood++;\n",
    "            }\n",
    "            traverse(node.left, max);\n",
    "            traverse(node.right, max);\n",
    "        }\n",
    "    }\n",
    "    \n",
    "    traverse(root, Number.NEGATIVE_INFINITY);\n",
    "    \n",
    "    return numGood;\n",
    "};"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "2f150dea",
   "metadata": {},
   "source": [
    "## Validate Binary Search Tree\n",
    "\n",
    "* https://leetcode.com/problems/validate-binary-search-tree/\n",
    "***\n",
    "* Time Complexity: O(n)\n",
    "    - must visit every node in the tree to determine if it fits the BST property\n",
    "* Space Complexity: O(height of tree):\n",
    "    - we use a recursive preorder traversal which uses a stack to store function calls\n",
    "    - the number of function calls will never exceed the height of the tree b/c it will go deeply down a branch of the tree until it reaches a leaf then returns\n",
    "***\n",
    "* similar to the good nodes problem but with a twist. you want to store the max and min nodes you've seen so far\n",
    "    - when you go down the left subtree, you want to update the max b/c the left subtree's nodes must never be greater than the node\n",
    "    - when you go down the right subtree, you want to update the min b/c the right subtree's nodes must never be lesser than the node\n",
    "    - and in addition to that, BOTH THE LEFT AND RIGHT SUBTREES MUST BE VALID BST FOR A NODE TO BE VALID AS WELL\n",
    "* also we know the root by itself will always be valid b/c there is no right and left subtree for it\n",
    "    - so we can just set it's min and max to negative infinity and positive infinity respectively"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 3,
   "id": "5d262fb8",
   "metadata": {},
   "outputs": [],
   "source": [
    "/**\n",
    " * Definition for a binary tree node.\n",
    " * function TreeNode(val, left, right) {\n",
    " *     this.val = (val===undefined ? 0 : val)\n",
    " *     this.left = (left===undefined ? null : left)\n",
    " *     this.right = (right===undefined ? null : right)\n",
    " * }\n",
    " */\n",
    "/**\n",
    " * @param {TreeNode} root\n",
    " * @return {boolean}\n",
    " */\n",
    "var isValidBST = function(root) {\n",
    "    const traverse = (node, min, max) => {\n",
    "        if (node === null) {\n",
    "            return true;\n",
    "        }\n",
    "        else {\n",
    "            if (!(min < node.val && node.val < max)) {\n",
    "                return false;\n",
    "            }\n",
    "            let left = traverse(node.left, min, node.val);\n",
    "            let right = traverse(node.right, node.val, max);\n",
    "            \n",
    "            return left && right;\n",
    "        }\n",
    "    }\n",
    "    \n",
    "    return traverse(root, Number.NEGATIVE_INFINITY, Number.POSITIVE_INFINITY);\n",
    "};"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "3910f0ac",
   "metadata": {},
   "source": [
    "## Kth Smallest Element in a BST\n",
    "\n",
    "* https://leetcode.com/problems/kth-smallest-element-in-a-bst/\n",
    "***\n",
    "* Time Complexity:\n",
    "    - recursive: O(n), traverse through the entire BST\n",
    "    - iterative: O(n), must also traverse through BST but will end early depending on its structure\n",
    "* Space Complexity:\n",
    "    - recursive: O(n), keeps an array of n elements inside it and also has a stack for function calls\n",
    "    - iterative: O(n), keeps a stack for inorder traversal of the tree\n",
    "***\n",
    "* recursive is easier to implement\n",
    "    - just do a typical inorder traversal\n",
    "    - add node's value to an array which will already make it sorted\n",
    "    - then return arr[k - 1]\n",
    "* iterative:\n",
    "    - same thing except you use a stack\n",
    "    - and once your k value reaches 0, you can then return the current node's value\n",
    "    - this has the added benefit of not having extra space be used for recursion and it's able to exit the loop earlier than recursive. so in the best case scenario, this would probably be closer to O(k)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 6,
   "id": "0915f6eb",
   "metadata": {},
   "outputs": [],
   "source": [
    "/**\n",
    " * Definition for a binary tree node.\n",
    " * function TreeNode(val, left, right) {\n",
    " *     this.val = (val===undefined ? 0 : val)\n",
    " *     this.left = (left===undefined ? null : left)\n",
    " *     this.right = (right===undefined ? null : right)\n",
    " * }\n",
    " */\n",
    "/**\n",
    " * @param {TreeNode} root\n",
    " * @param {number} k\n",
    " * @return {number}\n",
    " */\n",
    "\n",
    "// recursive inorder traversal\n",
    "// O(n) time\n",
    "// O(n) space\n",
    "var kthSmallest = function(root, k) {\n",
    "    let arr = [];\n",
    "    const traverse = (node) => {\n",
    "        if (node !== null) {\n",
    "            traverse(node.left);\n",
    "            arr.push(node.val);\n",
    "            traverse(node.right);\n",
    "        }\n",
    "    }\n",
    "    traverse(root);\n",
    "    return arr[k - 1];\n",
    "};\n",
    "\n",
    "// iterative inorder traversal\n",
    "// O(n) time)\n",
    "// O(n) space\n",
    "var kthSmallest = function(root, k) {\n",
    "    let stack = [];\n",
    "    let current = root;\n",
    "    \n",
    "    while (current || stack.length > 0) {\n",
    "        while (current) {\n",
    "            stack.push(current);\n",
    "            current = current.left;\n",
    "        }\n",
    "        \n",
    "        current = stack.pop();\n",
    "        k--;\n",
    "        if (k === 0) {\n",
    "            return current.val;\n",
    "        }\n",
    "        current = current.right;\n",
    "    }\n",
    "}"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "403f6f1b",
   "metadata": {},
   "source": [
    "## Construct Binary Tree from Preorder and Inorder Traversal\n",
    "\n",
    "* https://leetcode.com/problems/construct-binary-tree-from-preorder-and-inorder-traversal/\n",
    "***\n",
    "* Time Complexity: O(n)\n",
    "    - essentially just loop through the preorder and inorder arrays\n",
    "* Space Complexity: O(n)\n",
    "    - creating the subtree as you traverse so your tree will have n nodes\n",
    "    - and we're using recursion so there's a stack to keep track of function calls but this will probably be O(height of tree) since we build the left subtree first, then the right subtree\n",
    "***\n",
    "* preorder = root, Left, Right\n",
    "    - as you traverse through this, you'll be getting the current root\n",
    "* inorder = Left, root, Right\n",
    "    - if you have a preorder = [3, 9, 20, 15, 7] and your inorder = [9, 3, 15, 20, 7], if your current root = 3, then anything before 3 in inorder is the left subtree and anything after 3 is the right subtree\n",
    "* once you're finished with the current node, the indices to get the next root to work on follows this:\n",
    "    - if the leftsubtree is not empty, then it'll be index(current) + 1\n",
    "    - if the rightsubtree is not empty, it'll be index(current) + 1 + length(leftsubtree)\n",
    "        * reason being, there are cases in which the number after the leftsubtree's root is actually a part of the leftsubtree and not the root of the right subtree\n",
    "        * for example: preorder = [3, 1, 2, 4] and inorder = [1, 2, 3, 4]\n",
    "            - if current = 3, LS = [1, 2] and RS = [4]\n",
    "            - in preorder, we see that 1 and 2 are right next to each other and 4 is actually farther away\n",
    "            - so we need to account for the length of the left subtree in our calculation. it can't just be index(root) + 2"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 7,
   "id": "17f9b426",
   "metadata": {},
   "outputs": [],
   "source": [
    "/**\n",
    " * Definition for a binary tree node.\n",
    " * function TreeNode(val, left, right) {\n",
    " *     this.val = (val===undefined ? 0 : val)\n",
    " *     this.left = (left===undefined ? null : left)\n",
    " *     this.right = (right===undefined ? null : right)\n",
    " * }\n",
    " */\n",
    "/**\n",
    " * @param {number[]} preorder\n",
    " * @param {number[]} inorder\n",
    " * @return {TreeNode}\n",
    " */\n",
    "var buildTree = function(preorder, inorder) {\n",
    "    \n",
    "    const traverse = (inArr, root) => {\n",
    "        const current = preorder[root];\n",
    "        const newNode = new TreeNode(current);\n",
    "        const leftSubtree = [];\n",
    "        const rightSubtree = [];\n",
    "        let i = 0;\n",
    "        \n",
    "        // add all values to the left of the root to the leftSubtree array\n",
    "        while (i < inArr.length) {\n",
    "            if (inArr[i] === current) {\n",
    "                break;\n",
    "            }\n",
    "            leftSubtree.push(inArr[i]);\n",
    "            i++;\n",
    "        }\n",
    "        \n",
    "        // i will end on the current root's index\n",
    "        // so increment by one\n",
    "        i++;\n",
    "        \n",
    "        // will add all values to the right of the root to the rightSubtree array\n",
    "        while (i < inArr.length) {\n",
    "            rightSubtree.push(inArr[i]);\n",
    "            i++;\n",
    "        }\n",
    "        \n",
    "        // if the leftsubtree is not empty\n",
    "        // then the root will be the next item in preorder\n",
    "        let newRoot = root + 1;\n",
    "        if (leftSubtree.length > 0) {\n",
    "            newNode.left = traverse(leftSubtree, newRoot);\n",
    "        }\n",
    "        \n",
    "        // rightsubtree's root is root + 1 + leftsubtree.length away\n",
    "        // if the leftsubtree has multiple items, for example, then rightsubtree's root\n",
    "        // will not be next to the leftsubtree's root in preorder\n",
    "        newRoot += leftSubtree.length;\n",
    "        if (rightSubtree.length > 0) {\n",
    "            newNode.right = traverse(rightSubtree, newRoot);\n",
    "        }\n",
    "        \n",
    "        return newNode;\n",
    "    }\n",
    "    \n",
    "    return traverse(inorder, 0);\n",
    "};"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "id": "26ba0156",
   "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": "16.14.2"
  }
 },
 "nbformat": 4,
 "nbformat_minor": 5
}