Binary Search Tree Visualizer

How it works

1. Start at the root and compare the key you want with the key in the node.
2. Equal: you found it. Smaller: continue into the left subtree. Larger: continue into the right subtree.
3. Each comparison rules out the other subtree completely — the whole reason a BST is fast.
4. Search stops when it finds the key or steps onto an empty child, which proves the key is absent.
5. Insert makes the same walk and hangs the new key as a leaf on the empty child where the search ended.
6. Delete finds the node, then cuts off a leaf, lifts up a single child, or replaces a node that has two children with its in-order successor.

The ordering rule, and why it works

For every node, all keys in its left subtree are smaller and all keys in its right subtree are larger — not just its two children. Checking only left.key < node.key < right.key is a classic bug: a tree can pass that local test everywhere and still be broken, for example when a key deep in the root's left subtree is larger than the root.

Because the rule holds at every node, a search never needs to backtrack. At a node holding 50, a target of 42 cannot be anywhere to the right, so one comparison discards the entire right subtree — half of what is left, if the tree is balanced. The same rule is why an in-order traversal (left, node, right) prints the keys in sorted order, which doubles as a quick validity check.

Worked example: building and searching a tree

Insert 50, 30, 70, 20, 40, 60, 80, 35, 45, 90 into an empty tree — the tree the visualizer opens with. 50 becomes the root. 30 < 50 goes left and 70 > 50 goes right; then 20 and 40 settle under 30, and 60 and 80 under 70. For 35 the walk is 35 < 50 (left), 35 > 30 (right), 35 < 40 (left) — an empty spot, so 35 becomes 40's left child. 45 lands to the right of 40 and 90 to the right of 80: ten keys, four levels.

Searching for 45 compares 50 → 30 → 40 → 45: four comparisons out of ten keys. Searching for 55 compares 50 → 70 → 60 and then finds 60's left child empty — exactly where 55 would be inserted, which proves it is not stored. Run both searches above and watch the probe walk down.

Why the shape matters: O(log n) or O(n)

Every operation follows one root-to-leaf path, so its cost is proportional to the height h. A tree with n keys can be as short as ⌈log₂(n + 1)⌉ levels or as tall as n levels, and a plain BST has no say in which one it gets — the insertion order decides.

• Random order is kind: the average key ends up about 2 ln n ≈ 1.39·log₂ n levels deep, so searches are O(log n) on average.
• Sorted order is the worst case: each new key becomes the right child of the previous one and the tree degenerates into a linked list. Insert 1 to 7 and the tree is 7 levels tall, where a balanced tree needs 3. Try the Skewed preset.

That is why production code rarely uses a plain BST. Self-balancing search trees — AVL trees, red-black trees and B-trees — repair their shape after each update and guarantee O(log n) whatever the input order.

BST vs AVL tree vs B-tree

The three trees on this site share the same search rule and differ in how hard they work to stay short:

• Binary search tree: no balancing at all. The simplest code; O(log n) on average but O(n) in the worst case. Good for learning and for data that arrives in random order.
• AVL tree: a BST that stores each node's height and keeps every balance factor in −1…+1 with rotations. Height stays below about 1.44·log₂ n, so every operation is O(log n) in the worst case.
• B-tree: not binary — each node holds up to m − 1 sorted keys and m children, and all leaves sit on the same level. Splits and merges keep it perfectly balanced, and its wide nodes match disk pages, which is why databases and file systems use B-trees and B+ trees.

Rule of thumb: in memory, use your language's balanced tree (Java's TreeMap and C++'s std::map are red-black trees); on disk, use a B+ tree; use a plain BST to understand the idea — everything else builds on it.

Common mistakes and interview tips

• Validating a BST against children only. Pass an allowed (low, high) range down the recursion, or check that the in-order traversal is strictly increasing.
• Promising O(log n) without balancing. The follow-up question is always "what if the keys arrive sorted?" — the answer is height n and O(n) per operation.
• Deep recursion. Recursive insert or search on a degenerate tree recurses n levels deep and can overflow the call stack; iterative versions use O(1) extra space.

Interview favourites built on these ideas: the kth smallest key (in-order traversal with a counter), lowest common ancestor (the first node where the two keys go different ways), floor and ceiling of a key, and building a balanced BST from a sorted array (make the middle element the root, recurse on both halves).

Time and space complexity

Binary Search Tree in Python

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


def insert(root, key):
    """Insert key; returns the (possibly new) root."""
    if root is None:
        return Node(key)               # empty tree: the new node is the root
    cur = root
    while cur is not None:
        if key == cur.key:
            return root                # duplicate: keys are unique
        parent = cur
        if key < cur.key:
            cur = cur.left
        else:
            cur = cur.right
    # fell off the tree below parent: hang a new leaf there
    if key < parent.key:
        parent.left = Node(key)
    else:
        parent.right = Node(key)
    return root


def search(root, key):
    cur = root
    while cur is not None:
        if key == cur.key:
            return cur
        if key < cur.key:
            cur = cur.left             # everything on the right is too big
        else:
            cur = cur.right            # everything on the left is too small
    return None                        # fell off the tree: key is absent

The visualizer above shows the same code in Python, C++, Java and JavaScript.

Frequently asked questions

Keep learning

• Tree Traversal Visualizer — Inorder, Preorder, Postorder, Level OrderVisualize inorder, preorder, postorder and level-order tree traversal on one tree: the visit order, the call stack or queue, the code, and when to use each.
• BST Deletion — All Three CasesHow to delete a node from a binary search tree: the leaf, one-child and two-children cases, in-order successor or predecessor, with an animated example.
• AVL Tree VisualizerAVL tree visualizer: insert and delete keys, watch heights and balance factors update and LL, RR, LR, RL rotations keep every operation O(log n).
• B-Tree VisualizerB-tree visualizer: insert, search and delete keys in a B-tree of order 3 to 7, watch nodes split, borrow and merge, and see why databases are built on B-trees.
• Binary Heap VisualizerBinary heap visualizer: watch sift-up and sift-down in the tree and array side by side. Learn min-heap vs max-heap and O(log n) insert and extract, with code.
• Linked List VisualizerInteractive linked list visualizer: watch every pointer change as you insert, delete, search and reverse singly, doubly and circular lists, with code and costs.