Solve InterviewCake's second-largest-item-in-bst

Return a function that returns the second largest item in a binary search
tree (i.e. BST).

A BST is a tree where each node has no more than two children (i.e. one left
child and one right child). All of the values in a BST's left subtree must be
less than the value of the root node; all of the values in a BST's right subtree
must be greater than the value of the root node; both left and right subtrees
must also be BSTs themselves.

I solved this problem thrice -- improving the performance profile each time. The
final solution has a runtime complexity of O(n) and a spacetime complexity of
O(1).

2 files changed, 221 insertions, 2 deletions

diff --git a/scratch/deepmind/part_two/second-largest-item-in-bst.ts b/scratch/deepmind/part_two/second-largest-item-in-bst.ts
new file mode 100644
index 000000000000..4c5e57607d87
--- /dev/null
+++ b/scratch/deepmind/part_two/second-largest-item-in-bst.ts
@@ -0,0 +1,219 @@
+/*******************************************************************************
+ * Setup
+ ******************************************************************************/
+
+interface BinaryTreeNode {
+  value: number;
+  left: BinaryTreeNode;
+  right: BinaryTreeNode;
+}
+
+class BinaryTreeNode {
+  constructor(value: number) {
+    this.value = value;
+    this.left  = null;
+    this.right = null;
+  }
+
+  insertLeft(value: number): BinaryTreeNode {
+    this.left = new BinaryTreeNode(value);
+    return this.left;
+  }
+
+  insertRight(value: number): BinaryTreeNode {
+    this.right = new BinaryTreeNode(value);
+    return this.right;
+  }
+}
+
+/*******************************************************************************
+ * First solution
+ ******************************************************************************/
+
+/**
+ * I first solved this problem using O(n) space and O(n*log(n))
+ * time. InterviewCake informs me that we can improve both the time and the
+ * space performance.
+ */
+function findSecondLargest_first(node: BinaryTreeNode): number {
+  const stack: Array<BinaryTreeNode> = [];
+  const xs: Array<number> = [];
+  stack.push(node);
+
+  while (stack.length > 0) {
+    const node = stack.pop()
+
+    xs.push(node.value);
+
+    if (node.left) {
+      stack.push(node.left);
+    }
+    if (node.right) {
+      stack.push(node.right);
+    }
+  }
+
+  xs.sort();
+
+  if (xs.length < 2) {
+    throw new Error('Cannot find the second largest element in a BST with fewer than two elements.');
+  } else {
+    return xs[xs.length - 2];
+  }
+}
+
+/*******************************************************************************
+ * Second solution
+ ******************************************************************************/
+
+/**
+ * My second solution accumulates a list of the values in the tree using an
+ * in-order traversal. This reduces the runtime costs from O(n*log(n)) from the
+ * previous solution to O(n). The memory cost is still O(n), which InterviewCake
+ * informs me can be reduced to O(1).
+ */
+function findSecondLargest_second(node: BinaryTreeNode): number {
+  const xs: Array<number> = accumulateInorder(node);
+
+  if (xs.length < 2) {
+    throw new Error('Cannot find the second largest element in a BST with fewer than two elements.');
+  } else {
+    return xs[xs.length - 2];
+  }
+}
+
+/**
+ * Returns an array containing the values of the tree, `node`, sorted in-order
+ * (i.e. from smallest-to-largest).
+ */
+function accumulateInorder(node: BinaryTreeNode): Array<number> {
+  let result = [];
+
+  if (node.left) {
+    result = result.concat(accumulateInorder(node.left));
+  }
+  result.push(node.value)
+  if (node.right) {
+    result = result.concat(accumulateInorder(node.right));
+  }
+
+  return result;
+}
+
+/*******************************************************************************
+ * Third solution
+ ******************************************************************************/
+
+/**
+ * Returns the largest number in a BST.
+ */
+function findLargest(node: BinaryTreeNode): number {
+  let curr: BinaryTreeNode = node;
+
+  while (curr.right) {
+    curr = curr.right;
+  }
+
+  return curr.value;
+}
+
+/**
+ * Returns the second largest number in a BST
+ */
+function findSecondLargest(node: BinaryTreeNode): number {
+  let curr = node;
+  let parent = null;
+
+  while (curr.right) {
+    parent = curr;
+    curr = curr.right
+  }
+
+  if (curr.left) {
+    return findLargest(curr.left);
+  }
+  else {
+    return parent.value;
+  }
+}
+
+
+// Tests
+let desc = 'full tree';
+let treeRoot = new BinaryTreeNode(50);
+let leftNode = treeRoot.insertLeft(30);
+leftNode.insertLeft(10);
+leftNode.insertRight(40);
+let rightNode = treeRoot.insertRight(70);
+rightNode.insertLeft(60);
+rightNode.insertRight(80);
+assertEquals(findSecondLargest(treeRoot), 70, desc);
+
+desc = 'largest has a left child';
+treeRoot = new BinaryTreeNode(50);
+leftNode = treeRoot.insertLeft(30);
+leftNode.insertLeft(10);
+leftNode.insertRight(40);
+rightNode = treeRoot.insertRight(70);
+rightNode.insertLeft(60);
+assertEquals(findSecondLargest(treeRoot), 60, desc);
+
+desc = 'largest has a left subtree';
+treeRoot = new BinaryTreeNode(50);
+leftNode = treeRoot.insertLeft(30);
+leftNode.insertLeft(10);
+leftNode.insertRight(40);
+rightNode = treeRoot.insertRight(70);
+leftNode = rightNode.insertLeft(60);
+leftNode.insertRight(65);
+leftNode = leftNode.insertLeft(55);
+leftNode.insertRight(58);
+assertEquals(findSecondLargest(treeRoot), 65, desc);
+
+desc = 'second largest is root node';
+treeRoot = new BinaryTreeNode(50);
+leftNode = treeRoot.insertLeft(30);
+leftNode.insertLeft(10);
+leftNode.insertRight(40);
+rightNode = treeRoot.insertRight(70);
+assertEquals(findSecondLargest(treeRoot), 50, desc);
+
+desc = 'descending linked list';
+treeRoot = new BinaryTreeNode(50);
+leftNode = treeRoot.insertLeft(40);
+leftNode = leftNode.insertLeft(30);
+leftNode = leftNode.insertLeft(20);
+leftNode = leftNode.insertLeft(10);
+assertEquals(findSecondLargest(treeRoot), 40, desc);
+
+desc = 'ascending linked list';
+treeRoot = new BinaryTreeNode(50);
+rightNode = treeRoot.insertRight(60);
+rightNode = rightNode.insertRight(70);
+rightNode = rightNode.insertRight(80);
+assertEquals(findSecondLargest(treeRoot), 70, desc);
+
+desc = 'one node tree';
+treeRoot = new BinaryTreeNode(50);
+assertThrowsError(() => findSecondLargest(treeRoot), desc);
+
+desc = 'when tree is empty';
+treeRoot = null;
+assertThrowsError(() => findSecondLargest(treeRoot), desc);
+
+function assertEquals(a, b, desc) {
+  if (a === b) {
+    console.log(`${desc} ... PASS`);
+  } else {
+    console.log(`${desc} ... FAIL: ${a} != ${b}`)
+  }
+}
+
+function assertThrowsError(func, desc) {
+  try {
+    func();
+    console.log(`${desc} ... FAIL`);
+  } catch (e) {
+    console.log(`${desc} ... PASS`);
+  }
+}
diff --git a/scratch/deepmind/part_two/todo.org b/scratch/deepmind/part_two/todo.org
index 97b5e6fad3c2..a2ce2fb23dff 100644
--- a/scratch/deepmind/part_two/todo.org
+++ b/scratch/deepmind/part_two/todo.org
@@ -23,7 +23,7 @@
 * Trees and graphs
 ** DONE Balanced Binary Tree
 ** DONE Binary Search Tree Checker
-** TODO 2nd Largest Item in a Binary Search Tree
+** DONE 2nd Largest Item in a Binary Search Tree
 ** TODO Graph Coloring
 ** TODO MeshMessage
 ** TODO Find Repeat, Space Edition BEAST MODE
@@ -34,7 +34,7 @@
 ** TODO The Cake Thief
 ** DONE Balanced Binary Tree
 ** DONE Binary Search Tree Checker
-** TODO 2nd Largest Item in a Binary Search Tree
+** DONE 2nd Largest Item in a Binary Search Tree
 * Queues and stacks
 ** TODO Largest Stack
 ** TODO Implement A Queue With Two Stacks