Binary Search Tree Visualizer
Insert, delete and search keys in a binary search tree and watch every comparison, then run in-order, pre-order, post-order and level-order traversals. Each operation is counted and explained, including all three deletion cases.
How to Use
- Pick an operation in the bar: Insert, Delete, Search or Traverse.
- Type a key (a whole number from −999 to 9999) and press the button or Enter. Insert also takes a list such as
50, 30, 70, inserted left to right. - Watch the path: each node the key is compared with lights up, the narration says which way it went, and Back, Next and Replay step through it again.
- For a traversal choose In-order, Pre-order, Post-order or Level-order; the nodes are numbered in the order they are visited and the output builds up underneath.
- Read the readouts (nodes, height against the best possible height, comparisons for the last operation, balanced or not) and Show Work for every comparison and every relinking step.
- Share a tree: the address keeps
?insert=for the keys and?op=,?key=or?order=for the last operation.
Worked Example
Build a tree from 50, 30, 70, 20, 40, 60, 80. 50 becomes the root (0 comparisons). 30 < 50, left (1). 70 > 50, right (1). 20 < 50, 20 < 30, left of 30 (2). 40 < 50, 40 > 30, right of 30 (2). 60 > 50, 60 < 70, left of 70 (2). 80 > 50, 80 > 70, right of 70 (2). Total 10 comparisons; 7 nodes in 3 levels, height 2, which is the best possible: ⌈log₂(7 + 1)⌉ − 1 = 3 − 1 = 2.
Search. Searching for 60: 60 > 50, right; 60 < 70, left; 60 = 60, found after 3 comparisons. Searching for 65: 65 > 50, right; 65 < 70, left; 65 > 60, right, but the right link of 60 is empty: a search miss, also 3 comparisons, ending exactly where Insert 65 would attach it. Run the miss.
Delete 50, the root, which has two children (Hibbard deletion). Finding 50 takes 1 comparison. Its in-order successor is the smallest key in its right subtree: go right to 70, then left to 60, which has no left child. 70’s left link takes 60’s right subtree (empty), and 60 moves into the root with 30 and 70 as its children. The tree is now 60 at the root, 30 (with 20 and 40) on the left and 70 (with 80) on the right: in-order 20, 30, 40, 60, 70, 80, still sorted, and height still 2. Run this deletion.
The common mistake: “a BST is O(log n)”. Only a balanced one is. Insert the same kind of keys in sorted order, 1, 2, 3, 4, 5, 6, 7, and each new key is larger than everything before it, so it goes right at every node: 0 + 1 + 2 + 3 + 4 + 5 + 6 = 21 comparisons to build, and the tree is a chain of height 6 instead of 2. Finding 7 now takes 7 comparisons instead of at most 3, and the average search over the 7 keys costs (1 + 2 + … + 7) / 7 = 28 / 7 = 4 comparisons against (1 + 2 + 2 + 3 + 3 + 3 + 3) / 7 = 17 / 7 = 2.43 in the balanced tree. With 1,000 sorted keys the worst search is 1,000 comparisons against 10. Build the degenerate tree.
Show Work
How It Works
Counting rules. A comparison is one test of the key against a node’s key, so every node on the search path counts once, the matching node included. Following links to find the successor in a deletion compares no keys and is shown separately. A traversal makes no comparisons; its readout counts the nodes visited. Inserting a key that is already in the tree changes nothing (algs4’s put() would only update the stored value).
Sources: R. Sedgewick and K. Wayne, Algorithms, 4th ed., §3.2 Binary Search Trees (definition, search, insert, Hibbard deletion, in-order traversal, the 2 ln n proposition and the height proposition), BST.java, §3.3 Balanced Search Trees and the Algorithms and Data Structures Cheatsheet (symbol-table costs, the T(n) = 2T(n/2) + 1 tree-traversal recurrence).
Background
The deletion rule this tool uses is named after Thomas N. Hibbard. Sedgewick and Wayne credit him with first proposing, in 1962, that a node with two children be replaced by its successor; his paper “Some Combinatorial Properties of Certain Trees With Applications to Searching and Sorting” appeared in the Journal of the ACM, volume 9, issue 1, pages 13–28, in January 1962.
The rule works but is not symmetric: it always takes the successor, never the predecessor. algs4 shows the effect with a tree of 150 random keys put through repeated random Hibbard deletions and insertions: the tree becomes skewed to one side, and their cheatsheet gives √n as the average cost of a delete, against log n for search and insert.
The lasting fix is a tree that rebalances itself. Section 3.3 of algs4 builds the left-leaning red-black BST, which encodes a 2-3 tree in an ordinary binary tree and guarantees height no more than 2 lg n, so search, insert and delete are logarithmic in the worst case; the cheatsheet lists AVL trees with the same guarantees. If you need a sorted map in practice, use a library tree of this kind rather than a plain BST.
About This Tool
This visualizer keeps a real binary search tree of whole-number keys and draws it with every node in its in-order position, so the left-to-right order on screen is always the sorted order. Insert, delete and search animate the comparison path one node at a time; traversals number the nodes as they are visited and build the output sequence.
What it adds to a drawing: exact comparison counts with stated rules, all three deletion cases with the successor path and every relinking step written out, the height checked against the best possible height, a balance check that names the node where it fails, and an address that rebuilds the same tree. Everything runs in your browser; nothing you type is uploaded.
It is for students tracing BST operations for a data-structures course, people preparing for coding interviews, and teachers who want to show why sorted input ruins an unbalanced tree.
Related tools: Big-O Complexity Chart, Sorting Algorithm Visualizer, and Graph Theory Lab.
Frequently Asked Questions
Why is a binary search tree sometimes O(n) and not O(log n)?
The cost of search, insert and delete is proportional to the height of the tree (algs4 §3.2), and the height depends on the order the keys arrive in. Insert 50, 30, 70, 20, 40, 60, 80 and the 7 nodes sit in 3 levels, height 2. Insert 1, 2, 3, 4, 5, 6, 7 and every key goes to the right of the last one: height 6, a linked list, and searching for 7 takes 7 comparisons instead of 3. For 1,000 sorted keys the worst search is 1,000 comparisons against 10 in a perfectly balanced tree. Keys in random order give about 2 ln n comparisons on average (13.8 for n = 1,000); red-black and AVL trees guarantee O(log n) whatever the order.
How do you delete a node that has two children?
With Hibbard deletion, the method in algs4 §3.2 and the one this tool uses. A leaf is simply removed, and a node with one child is replaced by that child. A node with two children is replaced by its in-order successor, the smallest key in its right subtree: go right once, then left as far as possible. In the tree 50, 30, 70, 20, 40, 60, 80, deleting 50 goes right to 70, then left to 60; 60 moves into the root, 70’s left link becomes empty, and the tree keeps height 2. The successor has no left child, so removing it from its old place is always one of the two easy cases.
What is the difference between in-order, pre-order, post-order and level-order?
They visit the same nodes in different orders. For the tree built from 50, 30, 70, 20, 40, 60, 80: in-order (left, node, right) gives 20, 30, 40, 50, 60, 70, 80, the keys sorted; pre-order (node, left, right) gives 50, 30, 20, 40, 70, 60, 80; post-order (left, right, node) gives 20, 40, 30, 60, 80, 70, 50; level-order (top to bottom, left to right, with a queue) gives 50, 30, 70, 20, 40, 60, 80. Inserting the pre-order sequence into an empty tree rebuilds exactly the same tree, which is how this page stores a tree in its address.
How is the height counted, and what does balanced mean here?
Height is the number of edges on the longest path from the root down to a leaf: a single node has height 0. The smallest possible height for n nodes is ⌈log₂(n + 1)⌉ − 1, which is 2 for 7 nodes and 9 for 1,000. The tool calls a tree balanced when, at every node, the heights of the two subtrees differ by at most 1 (an empty subtree counts as −1). The sorted tree 1 to 7 fails at the root: its left subtree is empty (−1) and its right subtree has height 5.
What counts as a comparison, and what happens to duplicate keys?
One comparison is one test of the key against a node’s key, the compareTo() call in algs4’s BST.java, so a search makes one comparison per node on its path, whether it ends in a hit or at an empty link. Building the tree 50, 30, 70, 20, 40, 60, 80 takes 0 + 1 + 1 + 2 + 2 + 2 + 2 = 10 comparisons. A BST holds each key once: algs4’s put() overwrites the value of a key that is already there, so inserting 40 again here makes 3 comparisons and leaves the tree unchanged.
How do I use the Binary Search Tree Visualizer?
Simply type your numbers and read the result, which refreshes the instant you change something. There is nothing to submit and nothing to wait for.
Does it cost anything or need an account?
No. The tool is completely free, there is no account to create, and it keeps working offline after the page first loads.
Is anything I type uploaded?
No. The tool works entirely on your device, so the values you enter never leave your browser.
Common Use Cases
Check a homework trace
Insert the keys from the exercise and compare: 50, 30, 70, 20, 40, 60, 80 should take 10 comparisons and give pre-order 50, 30, 20, 40, 70, 60, 80.
See why balance matters
Load Sorted input 1–7: 21 comparisons to build, height 6 against a best of 2, and 7 comparisons to find 7. The balanced preset finds any key in at most 3.
Learn the deletion cases
Delete 20 (a leaf), then 70 from a tree where it has one child, then 50 (two children): Show Work names the case each time and, for case 3, the successor path 70 → 60.
Practise traversals for an exam
Predict the post-order of the balanced tree before pressing Traverse: 20, 40, 30, 60, 80, 70, 50. Level-order shows the queue before each of the 7 visits.
Explain a search miss
Search 65 in the balanced tree: 3 comparisons (50, 70, 60) end at the empty right link of 60, exactly where Insert 65 would put it.
Last updated: