Binary Search Tree Simulator
Insert, search and delete in a binary search tree step by step, including all three deletion cases and the in-order successor.
Operations
Binary search tree
Drag to move · scroll to zoom
In-order traversal (always sorted): 20, 30, 35, 40, 50, 60, 70, 80
Pseudocode
The current line is highlighted.
About This Simulation
This binary search tree (BST) simulator animates insertion, search and deletion one comparison at a time. Deletion covers all three cases, including replacing a node with its in-order successor, and the in-order traversal shows the values in sorted order.
Features
- Insert, search and delete with each comparison highlighted
- All three deletion cases: leaf, one child and two children
- In-order successor found and copied step by step
- Height, node count and worst-case search length
- Random trees and sorted input to show an unbalanced tree
- Pseudocode with the active line highlighted
Topics covered
- Binary Search Tree
- BST Insertion
- BST Search
- BST Deletion
- In-order Successor
- Balanced vs Unbalanced Trees
Explanation
A binary search tree is a binary tree where, for every node, all values in its left subtree are smaller and all values in its right subtree are larger. This ordering means each comparison can rule out a whole subtree, so searching a balanced tree takes about log₂ n steps.
How it works
- Search: start at the root. If the value is smaller go left, if larger go right, until you find it or reach an empty branch.
- Insert: search for the value; the empty branch where the search ends is where the new node goes.
- Delete a leaf: simply remove it.
- Delete a node with one child: replace the node with its child.
- Delete a node with two children: find the in-order successor (the smallest value in the right subtree), copy its value into the node, then delete the successor.
Why it matters
BSTs are on the Cambridge 9618 syllabus and in CSE220/CSE221. They give fast searching, insertion and deletion while keeping data sorted, and they lead on to self-balancing trees such as AVL and red-black trees used in databases and libraries.
Frequently Asked Questions
What is the time complexity of searching a BST?
O(h), where h is the height. For a balanced tree that is O(log n); for a degenerate tree built from sorted data it becomes O(n).
Why does in-order traversal of a BST give sorted output?
In-order visits the left subtree (all smaller values), then the node, then the right subtree (all larger values), so values come out in ascending order.
What is the in-order successor?
The next larger value in the tree. For a node with a right subtree, it is the leftmost (smallest) node in that subtree.
Why does inserting sorted data make a BST slow?
Each new value is larger than all previous ones, so it always goes to the right. The tree becomes a long chain, like a linked list.
Related Simulations
Data Structures
Binary Tree Simulator
Build a binary tree, run pre-order, in-order, post-order and level-order traversals step by step, and see its height and leaf nodes.
Data Structures
Heap Simulator
See min-heap and max-heap insertion, extraction and heapify as both a tree and an array, one swap at a time.
Algorithms
Searching Algorithms
Run linear, binary, ternary and quaternary search on your own array and step through the code one line at a time.
Data Structures
B+ Tree
Insert, delete, search in a B+ tree visualiser