From 319652fe08e50c00022b8caaa8ef357637393827 Mon Sep 17 00:00:00 2001 From: William Carroll Date: Mon, 16 Mar 2020 11:45:34 +0000 Subject: 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). --- .../part_two/second-largest-item-in-bst.ts | 219 +++++++++++++++++++++ scratch/deepmind/part_two/todo.org | 4 +- 2 files changed, 221 insertions(+), 2 deletions(-) create mode 100644 scratch/deepmind/part_two/second-largest-item-in-bst.ts (limited to 'scratch/deepmind') 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 = []; + const xs: Array = []; + 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 = 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 { + 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 -- cgit 1.4.1