Binary Search Tree

A node-based binary tree data structure which has the following properties: The left subtree of a node contains only nodes with keys lesser than the node's key. The right subtree of a node contains only nodes with keys greater than the node's key.

Ordered Trees

Binary search trees use ordering to cut down the search space

In a binary search tree, every node splits the remaining values into two groups: smaller values go left, larger values go right. Because of that rule, search, insert, and delete do not need to scan the whole structure. They only follow one path from the root downward.

How to read the demo

Read each comparison as a left-or-right decision.

The active node is the value currently being compared with the target.

If the target is smaller, the algorithm moves left. If it is larger, the algorithm moves right.

The log explains each step of the path so the decision process stays visible.

What to try in the demo

Use the same number with search, insert, and delete to compare behaviors.

Search for a value that exists, then search for one that does not.

Insert a new value and notice that it always lands at the end of one search path.

Toggle Worst Case to see why a skewed tree loses the advantage of balanced branching.

Visualize traversal, comparisons, and the 3 cases of deletion.

Controls

Tree Visualization

BST rule: left < node < right

Current Decision

Enter a value and choose an action to follow one BST decision path from the root.

Tree Height: 2|Comparisons: 0|Mode: Balanced Example

Why BSTs Matter

In an ideal (balanced) BST, operations are O(log N) because each comparison eliminates half the remaining nodes. If you insert sorted values in Worst Case mode, the tree becomes skewed like a linked list, degrading toward O(N).

Operations

One ordering rule powers search, insert, and delete

All three operations begin with the same idea: compare the current node to the target and discard the half that cannot contain the answer.

Follow one path until you find the value or hit null.

Fast when the tree stays balanced.

Only one subtree matters after each comparison.

Insert

Search for the correct gap, then attach the new node.

The path is the same as search until an empty child appears.

The BST rule remains true after insertion.

Delete

Deletion depends on how many children the node has.

Leaf and one-child cases are direct rewires.

Two-child deletion usually uses the inorder successor.

Operation	Core Rule	Why It Helps
Search	Compare the target with the current node and move left or right.	Each comparison throws away one whole subtree.
Insert	Follow the same search path until you find an empty child position.	The ordering rule stays true after the new node is attached.
Delete	Handle leaf, one-child, and two-child cases differently.	The tree keeps its search property after rewiring or replacement.
Worst-case mode	Watch what happens when the tree becomes skewed instead of balanced.	BST performance can fall from near O(log n) toward O(n).

Key Takeaways

The short version

A BST keeps smaller values on the left and larger values on the right.
That ordering turns search into a sequence of left-or-right decisions.
Insert follows the same path as search until it finds an empty spot.
Delete is more subtle because the tree must stay ordered after the node is removed.