DEV Community

Devanshu Biswas
Devanshu Biswas

Posted on • Originally published at github.com

I built a binary search tree visualizer: watch insert, search, the tricky two-child delete, and why in-order is sorted

#algorithms #javascript #computerscience #datastructures

A binary search tree is one of those data structures that's simple to state and easy to get subtly wrong when you code it — especially delete. So I built one you can watch: insert, search and delete walk the tree by comparison, and all four traversals animate their visit order.

▶ Live demo: https://dev48v.github.io/binary-search-tree/
Source: https://github.com/dev48v/binary-search-tree

The one rule

Every node obeys: left subtree < node < right subtree. That's the whole data structure. It's why you never scan the tree — at each node you compare and turn one way:

search(v):
  cur = root
  while cur:
    if v == cur.val: return found
    cur = v < cur.val ? cur.left : cur.right
Enter fullscreen mode Exit fullscreen mode

The number of comparisons is the depth, not the size. On a balanced tree of a million nodes that's ~20 steps. In the demo, search lights up exactly that path.

Delete is the part that trips people up

Insert and search are easy walks. Delete has three cases, and the third is the one everyone half-remembers:

  1. Leaf — just remove it.
  2. One child — replace the node with its child.
  3. Two children — replace the node's value with its in-order successor: the smallest value in its right subtree. Then delete that successor from the right subtree (it has at most one child, so it falls into case 1 or 2).

Why the successor? Because it's the very next value in sorted order, so slotting it in keeps left < node < right true everywhere. Any other choice breaks the invariant. The demo tells you when this happens — "replaced by in-order successor 40" — so you can see the swap.

delete(node with two children):
  succ = min(node.right)     // smallest on the right
  node.val = succ.val        // copy it up
  node.right = delete(node.right, succ.val)   // remove the original
Enter fullscreen mode Exit fullscreen mode

The four traversals, and why in-order is special

Depth-first traversals differ only in when you visit the node relative to its children:

  • in-order (Left → Node → Right) → visits values in sorted order. This is the party trick: an in-order traversal of a BST is a sort. Run it in the demo and the output is always ascending.
  • pre-order (Node → Left → Right) → visit the node first; used to copy or serialize a tree (you can rebuild it from a pre-order + structure).
  • post-order (Left → Right → Node) → visit the node last; used to free/delete a tree bottom-up, so you never orphan a child.
  • level-order (breadth-first) → visit row by row using a queue; how you'd print a tree level by level.

The catch worth seeing

Insert 1, 2, 3, 4, 5 in order and the tree doesn't branch — each value is bigger than the last, so it strings down the right side into a linked list with height = n. Now search is O(n), not O(log n). That degenerate case is the entire reason self-balancing trees (AVL, red-black) exist: they rotate on insert to keep the height ~log n no matter the input order. Watch a BST degenerate once and balanced trees stop being abstract.

Insert some values, run in-order to see them sorted, then delete a node with two children and watch the successor take its place. If it made BSTs click, a star helps others find it: https://github.com/dev48v/binary-search-tree

Top comments (0)