∿ExploreSims
ExploreSims / Computer Science & Technology / Data Structures / Binary Search Trees
Premium experiment • ordered search paths

COMPUTER SCIENCE & TECHNOLOGY • DATA STRUCTURES

Binary Search Trees

Insert keys one at a time, watch the tree shape emerge, and follow comparison paths while searching for a target.

● TREE INSERTIONOrdered search structure
Nodes
Height
Search result
Inorder traversal

Reasoning inspector

live model state
Tree size—
Tree height—
Search target—
Found—
Search path—
Comparisons—
Inorder—
Preorder—
Postorder—

Insertion order shapes performance

A basic binary search tree preserves ordered search, but its height depends on insertion order because this model performs no automatic balancing.

LEARN WITH THE SIMULATION

Understand Binary Search Trees by experimenting.

START HERE

A binary search tree stores ordered keys so each comparison can discard one side of the current node, but the efficiency of that idea depends on tree shape. This premium laboratory builds a tree insertion by insertion, highlights the exact search path for a target, reports height and comparison count, and exposes inorder, preorder and postorder traversals. A comparison-budget challenge turns insertion order into an algorithmic design problem rather than a decorative tree drawing.

BUILD THE IDEA

What you should understand first

  • Apply the BST invariant left<node<right during insertion and search.
  • Trace each target comparison from root to child until the key is found or a null branch is reached.
  • Connect insertion order with tree height and search-path length.
  • Use inorder traversal as a structural check that the stored distinct keys appear in sorted order.

TRY IT YOURSELF

How can the same set of keys require a few comparisons in one BST and almost a linear scan in another?

  1. Build the default mixed-order sequence and record tree height and comparisons for a target.
  2. Re-enter the same keys in sorted order and rebuild the tree.
  3. Search the same target and compare the highlighted path.
  4. Choose a more balanced insertion order and attempt to meet the comparison budget.
Read the visual:

A plain BST preserves ordering but does not rebalance itself. Sorted insertion can create a one-sided chain with height near n−1, while a balanced-looking insertion order keeps height and search paths much shorter for the same key set.

WHY IT WORKS 01

Search cost follows a root-to-node path

At each node the target is compared with the node key; smaller targets go left and larger targets go right. The number of comparisons is therefore the number of visited nodes on that path. In a shallow tree this can be logarithmic-like, while a degenerate chain can require a number of comparisons proportional to the number of stored keys.

WHY IT WORKS 02

Insertion order determines shape in an unbalanced BST

The BST rule determines where a new key belongs relative to the existing nodes, but it does not choose a globally balanced shape. Inserting sorted values repeatedly selects the same side and forms a chain. Inserting median-like split keys early can create shorter subtrees and reduce later search paths without changing the final sorted set.

WHY IT WORKS 03

Traversals reveal different structural information

Inorder traversal visits left subtree, node and right subtree, so a valid BST yields sorted keys. Preorder begins with each subtree root and can help reconstruct insertion-like structure, while postorder visits children before the node. Seeing all three alongside the drawn tree connects recursive definitions with concrete orderings.

DO NOT MIX THESE UP

Common misconception

A basic binary search tree is not automatically balanced, and the BST invariant alone does not guarantee logarithmic search time. Inorder traversal being sorted verifies ordering but does not reveal whether the tree is balanced. Duplicate values are ignored by this model rather than stored as separate nodes.

PRACTICE CHALLENGE

Can you reorder the same keys so a chosen target is found within a strict comparison budget?

  • Build the full tree and record the highlighted search path and comparison count.
  • Set a smaller comparison budget.
  • Reorder the same insertion sequence without changing the key set.
  • Rebuild and verify whether tree height and target path now satisfy the budget.
Reveal the reasoning

The search comparisons equal the number of nodes visited from root toward the target. Reordering insertions changes which keys become early ancestors, so the same key set can produce very different heights and paths. Placing useful split values earlier can shorten the target path, although a self-balancing tree would automate such structural control.

MODEL BOUNDARIES

What this simulation assumes

Every simulation simplifies reality or a mathematical system. These are the assumptions and limits to keep in mind while interpreting the results.

Model assumptions

  • Keys are integer values inserted sequentially into an initially empty unbalanced binary search tree.
  • Duplicate values are ignored after the first insertion.
  • Search compares the target with one node at a time and follows the standard left-smaller/right-larger invariant.

Model limitations

  • Self-balancing rotations, deletion, parent pointers, memory allocation costs and concurrent updates are omitted.
  • Node positions are chosen for teaching readability rather than by a production tree-layout algorithm.

CONNECT IT

Where this matters

  • Ordered sets and maps
  • Search indexes
  • Compiler and interpreter data structures
  • Foundations for AVL and red-black trees

WORDS THAT MATTER

Key vocabulary

Binary search tree
Ordered binary tree with smaller keys in each node’s left subtree and larger keys in its right subtree.
Tree height
Maximum edge depth from root to a descendant leaf in this model.
Search path
Sequence of node keys compared while following BST ordering toward a target.
Inorder traversal
Left-node-right traversal that yields sorted keys in a valid BST.
Degenerate tree
Highly unbalanced BST whose shape approaches a linked list and loses logarithmic-like search performance.