What is a binary search tree?
A binary search tree (BST) keeps values ordered: for every node, everything in its left subtree is smaller and everything in its right subtree is larger. Searching, inserting and deleting follow a single path from the root, so the cost depends on the height h of the tree.
If values arrive in sorted order, a plain BST degrades into a chain with height n. An AVL tree fixes this by rotating nodes after each insert or delete so the left and right heights of every node differ by at most 1, which keeps the height close to log n.
Time complexity
| Operation | Time | Notes |
|---|---|---|
| Search, insert, delete (BST) | O(log n) average, O(n) worst | The worst case is a lopsided tree |
| Search, insert, delete (AVL) | O(log n) | Rotations keep the tree balanced |
| Find min or max | O(h) | Keep going left or right |
| Any traversal | O(n) | Visits every node once |
Try it yourself
- Insert a few values and read each comparison in the Output box.
- Delete a leaf, a node with one child and a node with two children to see the three cases.
- Switch to AVL, then insert 10, 20 and 30 to see a rotation.
- Run Inorder to see the values come out sorted.
Binary search tree vs hash table
A BST keeps keys in sorted order, so it supports range queries, minimum, maximum and ordered traversal. A hash table is faster for exact lookups on average, but it keeps no order.
Common questions
- What is a binary search tree?
- A binary tree in which the left subtree of a node holds smaller values and the right subtree holds larger values.
- What are inorder, preorder and postorder traversals?
- They are depth-first orders. Inorder is left, node, right and gives sorted output for a BST. Preorder is node, left, right. Postorder is left, right, node.
- What is the difference between a BST and an AVL tree?
- An AVL tree is a self-balancing BST that rotates nodes to keep its height about log n, so it never degrades into a chain.