Explore BST insertion, search, deletion, and traversal with animated comparisons, responsive controls, and live tree statistics.
Every comparison chooses a branch: values smaller than a node go left; values larger go right. Watch the route before the tree changes.
Tree controls
Build
Find
Traverse
Tree stage
Your tree is waiting.
Insert a number to grow from the root, or load the demo to start exploring immediately.
Traversal output
Under the hood
Choose an operation, then inspect the small Java sketch that drives the comparison or pointer update.
A Binary Search Tree keeps each left subtree smaller and each right subtree larger than its parent. Each comparison rules out half of the remaining choices-when the tree stays reasonably balanced.
Search / insert
O(h)
Inorder output
sorted
Worst-case height
O(n)
Concept guide
Review the mental model, tradeoffs, and practical use cases after you experiment.
A Binary Search Tree (BST) is an ordered tree structure maintaining the invariant where left child values are smaller and right child values are larger than their parent. Enables efficient search operations through value comparisons at each node.
Balanced tree structure
Linear tree (skewed)
Height-balanced operations
Node-based storage
Left < Root < Right
AVL/Red-Black variants
Insert: Find position using BST property
Delete: Handle leaf/one-child/two-children cases
Search: Traverse left/right based on values
Traversal: In-order returns sorted sequence
Balance: Rotations (for balanced variants)
| Variant | Advantages | Trade-offs |
|---|---|---|
| AVL Tree | Strict balance | Rotation overhead |
| Red-Black Tree | Efficient balance | Complex rules |
| Splay Tree | Self-optimizing | Unpredictable performance |
| Treap | Randomized balance | Priority management |
| Threaded BST | Efficient traversal | Extra pointer storage |
