Binary Search Tree Visualization — Step by Step

The ordering invariant

Every BST is built on one rule: for any node, every value in its left subtree is smaller, and every value in its right subtree is at least as large. The subtle word is *subtree* — the rule is not just about direct children. A node in the left subtree of 50 must be less than 50 even if it sits four levels down, because every insert compared it against 50 on the way in. This global invariant is what makes search work: one comparison at any node tells you which entire half of the tree to discard. In this visualizer, duplicates are allowed and are sent to the right subtree.

Insert: one comparison per level

Insert never rearranges existing nodes — it walks down from the root and attaches the new value at the first empty spot. Insert 50, 30, 70, 20, 40 in that order: 50 becomes the root. 30 is less than 50, so it goes left. 70 is greater, so it goes right. 20 goes left of 50, then left of 30. 40 goes left of 50 but right of 30, landing as 30's right child. The result is a perfectly balanced two-level tree — but only because the input arrived in a lucky order. This workspace is fully interactive: every value you insert persists in the tree for the next operation.

Search is binary search wearing a tree costume

Searching a BST is binary search with the 'middle element' choices frozen into the structure. Compare the target with the current node: equal means found, smaller means go left, larger means go right. Each comparison discards an entire subtree, exactly as binary search discards half the array. In a balanced tree with n nodes that is O(log n) comparisons — finding one value among a million takes about 20 steps. The payoff over a sorted array is that the tree also supports fast insertion and deletion, which an array cannot offer without shifting elements around.

Delete: the three cases

Deletion must remove a node without breaking the ordering invariant, and there are exactly three situations. Leaf node: just remove it. One child: splice the node out and connect its only child to its parent. Two children: the node cannot simply vanish, so replace its value with its *inorder successor* — the smallest value in its right subtree — then delete that successor from the right subtree instead. The successor has no left child by definition, so deleting it always falls into one of the first two cases. The visualizer's delete operation highlights the successor before swapping it in, so you can watch the hard case unfold.

The failure mode: sorted input

Feed a BST already-sorted input and the structure collapses. Insert 10, 20, 30, 40, 50: each value is larger than everything before it, so each becomes the right child of the previous one. The 'tree' is now a linked list leaning right, with height n, and every operation degrades from O(log n) to O(n) — a million-node search takes a million comparisons instead of 20. This is not a rare edge case; sorted or nearly-sorted input is common in real systems. It is exactly the problem self-balancing trees like the AVL tree were invented to solve: same interface, but rotations keep the height logarithmic.

JavaScript

class Node {
  constructor(value) {
    this.value = value;
    this.left = null;
    this.right = null;
  }
}

function insert(root, value) {
  if (root === null) return new Node(value);
  if (value < root.value) root.left = insert(root.left, value);
  else root.right = insert(root.right, value); // duplicates go right
  return root;
}

function search(root, value) {
  let node = root;
  while (node !== null) {
    if (value === node.value) return node;
    node = value < node.value ? node.left : node.right;
  }
  return null;
}

let root = null;
for (const v of [50, 30, 70, 20, 40]) root = insert(root, v);
console.log(search(root, 40) !== null); // true

Python

class Node:
    def __init__(self, value):
        self.value = value
        self.left = None
        self.right = None

def insert(root, value):
    if root is None:
        return Node(value)
    if value < root.value:
        root.left = insert(root.left, value)
    else:
        root.right = insert(root.right, value)  # duplicates go right
    return root

def search(root, value):
    node = root
    while node is not None:
        if value == node.value:
            return node
        node = node.left if value < node.value else node.right
    return None

root = None
for v in [50, 30, 70, 20, 40]:
    root = insert(root, v)
print(search(root, 40) is not None)  # True

Java

class BST {
    static class Node {
        int value;
        Node left, right;
        Node(int value) { this.value = value; }
    }

    Node root;

    void insert(int value) { root = insert(root, value); }

    private Node insert(Node node, int value) {
        if (node == null) return new Node(value);
        if (value < node.value) node.left = insert(node.left, value);
        else node.right = insert(node.right, value); // duplicates go right
        return node;
    }

    boolean search(int value) {
        Node node = root;
        while (node != null) {
            if (value == node.value) return true;
            node = value < node.value ? node.left : node.right;
        }
        return false;
    }

    public static void main(String[] args) {
        BST tree = new BST();
        for (int v : new int[] { 50, 30, 70, 20, 40 }) tree.insert(v);
        System.out.println(tree.search(40)); // true
    }
}