Build challenges · 4 steps · javascript · python
Binary Search Tree
Construct a Binary Search Tree with node pointers, recursive insertion, lookup, in-order traversal, and 3-case deletion.
A Binary Search Tree (BST) is a node-based binary tree where every node satisfies the BST Invariant:
- All keys in the left subtree are strictly less than the node's key.
- All keys in the right subtree are strictly greater than the node's key.
In this build, you will construct a Binary Search Tree from scratch:
- Implement ordered node insertion (
insert). - Search keys with $O(\log n)$ branching (
search). - Traverse keys in sorted order (
inOrder) and find extremes (min/max). - Implement recursive 3-case node deletion (
delete).
The workspace
These files carry across every step. What you write in one step is what you start the next with.
- binary_search_tree.js
- harness.jsread-only
Steps · 0 of 4 done
Start anywhere. Open step 3 first and you are handed the reference build of steps 1 and 2, so every step stands on its own. Nothing here is locked behind anything else.
This build applies Trees and Recursion & Memoisation. Read the lesson first if it is unfamiliar — a recommendation, not a prerequisite.