diff options
| author | William Carroll <wpcarro@gmail.com> | 2020-03-16T11·45+0000 |
|---|---|---|
| committer | William Carroll <wpcarro@gmail.com> | 2020-03-16T11·45+0000 |
| commit | 319652fe08e50c00022b8caaa8ef357637393827 (patch) | |
| tree | 577e684642c9164faeb41b469c6165822f145952 /scratch/deepmind/part_two/todo.org | |
| parent | 56d8d1d7b2ac2e6ea15150f5b2e72a26b721d927 (diff) | |
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).
Diffstat (limited to 'scratch/deepmind/part_two/todo.org')
| -rw-r--r-- | scratch/deepmind/part_two/todo.org | 4 |
1 files changed, 2 insertions, 2 deletions
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 |