Binary Search Tree

Implement a BinarySearchTree class — a specialization of a binary tree that maintains an ordering invariant at every node: everything in the left subtree is smaller than the node, and everything in the right subtree is larger. That single rule turns lookup into binary search: at each node you compare, descend left or right, and discard the other half of the tree. Insert and delete must preserve the invariant, and delete is the operation that earns the hard tier — three structural cases, one of which (the two-child case) needs the in-order successor trick.

Signature

class BinarySearchTree {
  insert(value: number): void;
  search(value: number): boolean;
  delete(value: number): void;
  inorder(): number[]; // helper — returns values in sorted ascending order
}

Examples

const t = new BinarySearchTree();
[5, 3, 8, 1, 4, 7, 9].forEach((v) => t.insert(v));
t.search(4);  // true
t.search(6);  // false  (close, but not present — no "nearest" semantics)
t.inorder(); // [1, 3, 4, 5, 7, 8, 9]  — sorted, because that's what BST inorder gives you

// Delete a leaf — simplest case
t.delete(1);
t.inorder(); // [3, 4, 5, 7, 8, 9]

// Delete a node with one child — child takes the parent's slot
t.delete(9);          // 9 was a leaf already; deleting 8 next would have one child (7)
t.delete(8);
t.inorder(); // [3, 4, 5, 7]

// Delete a node with two children — replaced by its in-order successor
const u = new BinarySearchTree();
[5, 3, 8, 1, 4, 7, 9].forEach((v) => u.insert(v));
u.delete(3);          // 3 has children 1 and 4; successor is 4; 3's slot now holds 4
u.inorder(); // [1, 4, 5, 7, 8, 9]

Notes

• BST invariant — at every node, every value in the left subtree is strictly less than the node's value, and every value in the right subtree is strictly greater (with one exception, see duplicates below). The invariant must hold after every insert and delete.
• Duplicates — pick a convention and document it. This implementation sends duplicates right (so insert(5); insert(5) produces two 5 nodes, the second as the right descendant of the first). Other valid choices: reject duplicates, or store a count per node. Pick one and stay consistent.
• delete has three cases — leaf (unhook), one child (child replaces the node), two children (copy the in-order successor's value into the slot, then recursively delete the successor from the right subtree).
• delete on missing values is a no-op — no throw, no error; the tree is unchanged.
• Complexity is O(h) where h is the tree's height — O(log n) for a balanced tree, O(n) for a degenerate (chain-shaped) tree. This implementation does not self-balance; insert/search/delete are worst-case O(n). Self-balancing variants (AVL, red-black) are out of scope here.
• Numbers only — assume values are JavaScript numbers (no strings, no objects). The < and > operators behave predictably on numbers; on mixed or non-number values they coerce and the invariant becomes meaningless.