GradesUpgradeSign in

Electrical & Computer

Binary Search Tree Lab

A binary search tree keeps one simple promise: every value to the left of a node is smaller, every value to the right is larger. This lab lets you build one by inserting values and then SEARCH for a target — the path from the root lights up so you can see search skip half the remaining tree at every step, which is what makes lookups O(log n) in a balanced tree. Delete a node and watch all three classic cases handled (a leaf vanishes, a one-child node is bypassed, a two-child node is replaced by its in-order successor), with the tree staying sorted throughout. The catch is built in too: insert values in already-sorted order and the tree collapses into a lopsided chain of height n−1, where search degrades all the way back to O(n) — the very reason self-balancing trees exist. An in-order traversal of any BST always comes out sorted, and the height readout shows you exactly how good (or bad) your tree's shape is.

3

Height (edges)

12

Nodes

O(4)

Search ≈

In-order traversal is always sorted.

The method, with your numbers

The BST ordering invariant

  1. 1

    Walk from the root (one comparison per level)

    v < node ⇒ go left v > node ⇒ go right v = node ⇒ found

    search 45: 50 → left, 30 → right, 40 → right ⇒ not found in 3 comparisons

    The walk dead-ends exactly where the value would live — press Insert and it attaches right there.

  2. 2

    Bound the cost by the height

    comparisons ≤ h + 1

    3 ≤ 3 + 1 = 4

    A search visits at most one node per level, so BST search is O(height) — not O(n).

  3. 3

    Compare to a perfectly balanced tree

    h_min = ⌈log₂(n + 1)⌉ − 1

    h_min = ⌈log₂(12 + 1)⌉ − 1 = 3 your tree: h = 3

    Height 3 is the minimum possible for 12 nodes — the insertion order kept this tree balanced.

  4. 4

    Read off the sorted order for free

    inOrder(node) = inOrder(left), node, inOrder(right)

    inOrder = [10, 20, 25, 30, 35, 40, 50, 60, 65, 70, 80, 90] (n = 12 values, ascending)

    An in-order walk of any BST is always sorted — the quickest check that a tree really is one.

Drag any control above — every number here recalculates. Want this method for any problem? Step Sheets →

Every left child is smaller, every right child larger. That ordering lets search skip half the tree at each step — O(log n) when balanced. Insert values in sorted order, though, and the tree degrades into a chain (height = n−1) where search is back to O(n).

How to use this simulation

A binary search tree keeps one simple promise: every value to the left of a node is smaller, every value to the right is larger. This lab lets you build one by inserting values and then SEARCH for a target — the path from the root lights up so you can see search skip half the remaining tree at every step, which is what makes lookups O(log n) in a balanced tree. Delete a node and watch all three classic cases handled (a leaf vanishes, a one-child node is bypassed, a two-child node is replaced by its in-order successor), with the tree staying sorted throughout. The catch is built in too: insert values in already-sorted order and the tree collapses into a lopsided chain of height n−1, where search degrades all the way back to O(n) — the very reason self-balancing trees exist. An in-order traversal of any BST always comes out sorted, and the height readout shows you exactly how good (or bad) your tree&apos;s shape is.

Everything runs in your browser — no sign-up, no download. Change a value and the result updates instantly, so you can build a feel for how each input shapes the outcome. It pairs with Crameleon's practice exams and step sheets when you want to go from intuition to working the problems.