Deviopath › TypeScript

Binary Search Tree with Remove

Hard · Data Structures

Implement a binary search tree of unique numbers (smaller values go left):

- insert(value) returns false for a duplicate, otherwise inserts it as a new leaf and returns true.

- has(value) returns whether the value is in the tree.

- remove(value) returns false if missing. A node with no children is removed; a node with one child is replaced by that child; a node with two children takes the value of its in-order SUCCESSOR (the smallest value in its right subtree), and that successor node is removed from the right subtree.

- inOrder() returns all values in ascending order.

- height() returns the number of nodes on the longest root-to-leaf path (0 for an empty tree).

- rootValue() returns the root value or null.

The driver runBST(ops) is already written.

Next: LFU Cache