A binary search tree is where an interview stops being about loops and starts being about structure. It is the data structure behind ordered maps, range queries, and the database indexes that decide whether a query takes a millisecond or a minute. In a quant coding round, the BST tests whether you can keep an invariant intact while you mutate a recursive structure, which is exactly what insert and (above all) delete demand. This lesson defines the tree vocabulary, states the BST invariant and what it buys you, implements all four traversals, and then works our interview question Binary Search Tree (BST) end to end: a clean BinarySearchTree with insert, delete, find_min and find_max, plus a validator that proves the tree is correct.
Table of Contents
Already have an account? Log in!