See exactly how a binary search tree changes as you insert, delete and search. Switch between a plain BST, a self-balancing AVL tree and a red-black tree, watch every comparison, rotation and recoloring animate step by step, and walk the tree in-order, pre-order, post-order or level by level.
Last updated:
Traverse:
The tree is empty. Insert a value or generate a random tree.
Tree stats
Traversal output
Press a traversal button to walk the tree.
Step log
Insert a list of values
Whole numbers from -999 to 9999, separated by commas or spaces. Duplicates are skipped. Up to 63 nodes. Inserting 10, 20, 30… in order shows why plain BSTs need balancing.
Advertisement
Advertisement
How to use the Binary Search Tree Visualizer
Choose a tree type: binary search tree, AVL tree or red-black tree. Your values are rebuilt in the new structure.
Type a whole number and press Insert, Delete or Find. Each comparison is highlighted and explained under the tree.
Watch the rebalancing: AVL trees show balance factors and rotate when one reaches ±2; red-black trees recolor and rotate to keep their color rules.
Press a traversal button to visit the nodes in in-order, pre-order, post-order or level-order and copy the sequence.
Open Insert a list of values to build a tree from many numbers at once, then download it as an SVG image.
Time complexity of binary search trees
Tree
Search
Insert
Delete
Worst-case height
Rotations per insert
Binary search tree (unbalanced)
O(h), O(n) worst
O(h), O(n) worst
O(h), O(n) worst
n − 1
0
AVL tree
O(log n)
O(log n)
O(log n)
about 1.44·log₂(n + 2)
At most 1 single or double rotation
Red-black tree
O(log n)
O(log n)
O(log n)
2·log₂(n + 1)
At most 2
h is the height of the tree and n the number of keys. A perfectly balanced tree with n keys has height ⌈log₂(n + 1)⌉ − 1 edges; the stats panel shows this as "Best possible" so you can compare it with the current tree.
The four AVL rotation cases
Case
When it happens
Fix
Try inserting
Left-Left
Node is +2 and its left child is 0 or +1
Single right rotation at the node
30, 20, 10
Right-Right
Node is −2 and its right child is 0 or −1
Single left rotation at the node
10, 20, 30
Left-Right
Node is +2 and its left child is −1
Left rotation at the child, then right rotation at the node
30, 10, 20
Right-Left
Node is −2 and its right child is +1
Right rotation at the child, then left rotation at the node
10, 30, 20
Tips for learning with the visualizer
See degeneration: clear the tree, choose Binary search tree and insert 10, 20, 30, 40, 50 in order. Then switch to AVL to see the same keys rebuilt with height 2 instead of 4.
Red-black recoloring: insert 10, 20, 30, 15, 25, 5 into an empty red-black tree to see a rotation followed by recoloring cases where the uncle is red.
Delete cases: delete a leaf, a node with one child and a node with two children to compare the three BST deletion cases.
Check your homework: type the keys from an exercise into Insert a list of values and compare each traversal with your own answer.
Frequently asked questions
What is a binary search tree?
A binary search tree (BST) is a binary tree in which every node's key is larger than all keys in its left subtree and smaller than all keys in its right subtree. That ordering lets you find, insert or delete a key by following a single path from the root, so each operation takes time proportional to the tree's height.
Why do BSTs need balancing?
If keys arrive in sorted order, a plain BST degenerates into a linked list of height n − 1, and search becomes O(n). Self-balancing trees such as AVL and red-black trees restructure themselves with rotations so the height stays O(log n), keeping search, insert and delete fast in the worst case.
What is the difference between an AVL tree and a red-black tree?
An AVL tree keeps the heights of every node's two subtrees within 1 of each other, so it is more tightly balanced (height at most about 1.44·log₂ n) and lookups are slightly faster. A red-black tree uses node colors and allows height up to 2·log₂(n + 1), but needs fewer rotations on insert and delete. Many standard libraries use red-black trees for ordered maps and sets.
How does deleting a node with two children work?
The node is replaced by its in-order successor, the smallest key in its right subtree. The successor has no left child, so it can be unlinked easily and moved into the deleted node's position. This keeps the BST ordering intact. (Using the in-order predecessor, the largest key in the left subtree, works equally well.)
What does the balance factor mean?
In an AVL tree the balance factor of a node is height(left subtree) − height(right subtree). Valid AVL nodes have a balance factor of −1, 0 or +1. When an insert or delete makes it +2 or −2, the tree performs a single or double rotation at that node to restore balance.
Which traversal gives the keys in sorted order?
In-order traversal (left subtree, node, right subtree) visits the keys of a binary search tree in ascending order. Pre-order (node first) is useful for copying or serializing a tree, post-order (node last) for deleting it or evaluating expression trees, and level-order visits the tree row by row using a queue.
What are the red-black tree rules?
Every node is red or black, the root is black, a red node never has a red child, and every path from a node down to an empty (nil) leaf passes through the same number of black nodes, called the black height. Empty leaves count as black. These rules guarantee the longest path is at most twice the shortest.
Are all the tools on FreeToolCabin tested for quality and accuracy?
Yes! Every tool on our site undergoes automated Q/A testing in real browser environments to ensure high precision, correct output, and zero errors. If you happen to spot a bug or have a suggestion, please contact us at [email protected] and our team will review it right away.