Green = found / Yellow = searching path / Red = not found.
A binary search tree (BST) is a fundamental data structure in computer science where each node stores a value and has at most two children: every value in the left subtree is smaller than the node, and every value in the right subtree is larger. This ordering property means that searching, inserting, and deleting elements all take O(log n) time on average — the same asymptotic efficiency as binary search on a sorted array, but with the flexibility of a dynamically linked structure. BSTs underpin database indices, symbol tables in compilers, and the std::map container in C++.
This simulator allows you to insert, search, and delete values, view inorder/preorder/postorder traversals with step-by-step animation, and apply AVL balancing to convert a degenerate (linked-list) tree into a height-balanced one. The stats panel reports node count, tree height, and whether the tree satisfies the AVL balance criterion (|h_L − h_R| ≤ 1 at every node).
What is the time complexity of BST search?
In a balanced BST, search takes O(log n) time because each comparison halves the remaining candidates, just like binary search. In the worst case — when values are inserted in sorted order, producing a linear chain — the tree degenerates and search drops to O(n). This is why self-balancing variants such as AVL trees and red-black trees were invented.
What is an AVL tree and how does balancing work?
An AVL tree (named after Adelson-Velsky and Landis, 1962) is a self-balancing BST that maintains the invariant that the height difference between the left and right subtrees (the balance factor) is at most 1 at every node. When an insertion or deletion violates this, a rotation — either single (left or right) or double (left-right or right-left) — restores balance in O(log n) time without changing the BST ordering property.
What does inorder traversal produce?
Inorder traversal (left → root → right) visits every node in sorted ascending order. This is one of the most useful properties of a BST: a single O(n) traversal produces a sorted list. In contrast, preorder (root → left → right) is useful for serialising a tree, and postorder (left → right → root) is used when you need to process children before parents, such as when deleting an entire tree.
The balance factor (bf) of a node is defined as the height of its left subtree minus the height of its right subtree. In an AVL tree, bf must be −1, 0, or +1 for every node. The simulator displays "bf:x" beneath each node. A node with bf = +2 has a left-heavy imbalance and requires a right rotation (or left-right double rotation if the child is right-heavy).
If elements are inserted in strictly ascending or descending order — for example, 1, 2, 3, 4, 5 — the BST becomes a right (or left) chain with height n−1, identical in structure to a linked list. Every search then requires visiting all n nodes, giving O(n) time. Try inserting sorted values in this simulator and compare the height to a randomly ordered insertion of the same values.
Deleting a node in a BST has three cases: (1) the node is a leaf — simply remove it; (2) the node has one child — splice the child in place; (3) the node has two children — replace the node's value with the smallest value in its right subtree (the in-order successor), then delete that successor node, which is guaranteed to fall into case 1 or 2. This simulator implements all three cases.
Database management systems use B-trees (a generalisation of BSTs with multiple keys per node) for their disc-based indices, enabling O(log n) row lookups across millions of records. The Linux kernel uses red-black trees (another self-balancing BST) for scheduling tasks and managing virtual memory areas. C++'s std::map and std::set are typically implemented as red-black trees, guaranteeing O(log n) worst-case operations.
Both are tree-based data structures but with different ordering properties. A BST enforces the left-child-less-than-parent ordering throughout the entire tree, making search efficient. A heap only enforces the heap property between a parent and its immediate children (max-heap: parent ≥ children), making finding the minimum or maximum O(1) but arbitrary search O(n). Heaps are optimal for priority queues; BSTs are optimal for sorted dictionaries.
For a perfectly balanced BST with n nodes, height h = ⌊log₂ n⌋. An AVL tree guarantees height at most 1.44 × log₂(n+2), which is still O(log n). A red-black tree guarantees height at most 2 × log₂(n+1). These bounds are what make all operations O(log n) even in adversarial insertion orders.
Standard BST definitions exclude duplicates, but real implementations handle them in one of three ways: (1) ignore duplicates (as in this simulator); (2) allow duplicates in the right subtree (val ≤ parent goes right); (3) store a count alongside each node value. The choice affects deletion logic and traversal semantics, so it is typically fixed at design time to match the application's requirements.
This simulation builds a binary search tree live in your browser, so you can insert, search for and delete integer values and watch each comparison highlighted step by step. A plain BST gets its shape purely from insertion order, so it can degrade into a slow, chain-like tree; the AVL Balance button rewrites the same values into a height-balanced tree using rotations, so you can compare search behaviour before and after. The three traversal buttons reveal the classic inorder, preorder and postorder visiting orders, and the statistics panel reports node count, tree height and whether the AVL balance condition currently holds.
Each inserted value becomes a node placed left or right of its parent following the BST rule: smaller values go left, larger go right. Search highlights the comparison path in yellow, turning green when the value is found or red when it is absent, so you can see how many comparisons a lookup actually needs — O(log n) on average for a balanced tree, but O(n) for a badly skewed one.
Enter a value and press Insert, Search or Delete; use Random 10 to fill the tree quickly, or Clear to start again. Press AVL Balance to reshape the current values into a balanced tree via rotations, then compare the reported height before and after. The Inorder, Preorder and Postorder buttons animate each traversal order in the result box, whilst the stats panel tracks node count, height, balance status and the last operation performed.
Inorder traversal of any binary search tree always visits values in strictly ascending order — this single property is why BSTs keep sorted data efficiently searchable, insertable and deletable without ever needing a separate sort step. Practical descendants of the AVL tree modelled here, such as red-black trees, underpin the C++ std::map and Java's TreeMap.
The simulator compares the new value with the root: smaller goes left, larger goes right, repeating recursively until it reaches an empty spot, where a new node is created. This preserves the BST ordering property — every left descendant is smaller and every right descendant is larger than its ancestor — without any rebalancing.
It reads out every value with an inorder traversal, empties the tree, then reinserts those same values using AVL-style insertion, which applies left and right rotations whenever a node's left and right subtree heights differ by more than one. The values are unchanged, but the resulting shape is height-balanced, typically shrinking the tree's height considerably.
Inorder visits left subtree, then the node, then right subtree, producing values in sorted ascending order. Preorder visits the node first, then left, then right, which is useful for copying or serialising a tree. Postorder visits both subtrees before the node itself, the order needed when deleting an entire tree safely.
If values are inserted in already-sorted order, the plain BST grows into a one-sided chain no different from a linked list, so a lookup may have to check every node. Try inserting numbers in ascending order, note the reported height, then press AVL Balance to see the height and worst-case search cost collapse back down.
It is the node's balance factor: the height of its left subtree minus the height of its right subtree. An AVL tree keeps this value at −1, 0 or +1 for every node; a larger magnitude signals an imbalance that a rotation would need to correct.