Trees & BST
Binary Search Tree — smaller left, larger rightA binary tree is made of nodes that each have up to two children. In a binary search tree every node keeps smaller values on its left and larger values on its right — so a search can skip half of the tree at every step. Watch the key travel down the tree.
- Left subtreeevery value is smaller
- Right subtreeevery value is larger
- Searchone path from the root: O(h)
- Current
- Path
- Visited
- Found / new
- Removing
Ready
Keyboard: ← → step · Space play / pause · R reset · Esc exit classroom mode
Every operation, in plain steps
These are exactly the steps the visualizer animates.
What is a tree node?
Like a linked list node, but with two pointers: left and right. The top node is the root, nodes without children are leaves. In a binary SEARCH tree, everything in a node's left subtree is smaller and everything in its right subtree is larger. Height = the number of edges on the longest path from the root to a leaf.
struct Node {
int data;
struct Node *left; // smaller values
struct Node *right; // larger values
};
struct Node *root = NULL; // empty tree
Search
- Start at the root.
- Equal? Found it.
- Smaller? Go left. Larger? Go right.
- Reaching NULL means the value is not there.
Insert
- Walk down exactly like a search.
- When the next step is NULL, stop there.
- Create the node and link it in that spot.
- A new value always becomes a leaf.
Delete
- Leaf: just remove it.
- One child: link the parent straight to that child.
- Two children: copy in the inorder successor…
- …(smallest value on the right), then delete that successor.
Depth-first traversals
- Inorder: left → node → right (sorted order!).
- Preorder: node → left → right.
- Postorder: left → right → node.
- Recursion keeps a call stack of the nodes in progress.
Level order (BFS)
- Put the root in a queue.
- Take the front node and visit it.
- Add its children at the rear.
- Repeat until the queue is empty.
Balanced vs skewed
- Speed depends on the height h, not on n.
- Balanced: h ≈ log₂ n (15 nodes → 4 levels).
- Sorted input makes a skewed tree: h = n − 1.
- Self-balancing trees (AVL, Red-Black) keep h small.
Pseudocode
Language-independent steps. The visualizer shows the same logic in C, Python and Java.
How fast is each operation?
n = number of nodes, h = height. A balanced tree has h ≈ log n; a skewed tree has h = n − 1. Recursive traversals use O(h) stack space.
| Operation | Best | Average | Worst | Speed |
|---|---|---|---|---|
| Search | O(1) |
O(log n) |
O(n) |
Grows with n |
| Insert | O(1) |
O(log n) |
O(n) |
Grows with n |
| Delete | O(1) |
O(log n) |
O(n) |
Grows with n |
| Min / Max | O(1) |
O(log n) |
O(n) |
Grows with n |
| Any traversal | O(n) |
O(n) |
O(n) |
Grows with n |
The four traversals of 50, 30, 20, 40, 70, 60, 80
| Traversal | Order | Result | Used for |
|---|---|---|---|
| Inorder | left → node → right | 20 30 40 50 60 70 80 | Values in sorted order |
| Preorder | node → left → right | 50 30 20 40 70 60 80 | Copying / saving a tree |
| Postorder | left → right → node | 20 40 30 60 80 70 50 | Deleting a tree, evaluating expressions |
| Level order | level by level (queue) | 50 30 70 20 40 60 80 | Shortest paths, printing by level |
Searching: sorted array vs BST
| Sorted array | BST (balanced) | BST (skewed) | |
|---|---|---|---|
| Search | O(log n) — binary search | O(log n) | O(n) |
| Insert | O(n) — shift elements | O(log n) | O(n) |
| Delete | O(n) — shift elements | O(log n) | O(n) |
| Memory | Values only | Values + 2 pointers per node | Values + 2 pointers per node |
Try the "Skewed" button in the visualizer: sorted input turns the tree into a line.
Check your understanding
Answer each question — you will see the explanation straight away.
In a BST, where are all the values smaller than the root?
That is the BST rule: smaller values on the left, larger values on the right — for every node, not just the root.
Which traversal prints the values of a BST in sorted order?
Inorder visits the left subtree (smaller), then the node, then the right subtree (larger) — which is exactly sorted order.
You insert 10, 20, 30, 40, 50 into an empty BST in that order. What does the tree look like?
Each value is larger than all earlier ones, so it always goes right. Search in this tree is O(n) — no better than a list.
You delete a node that has two children. What replaces it?
The successor is larger than everything on the left and smaller than everything else on the right, so the BST rule still holds.
Which data structure does level order traversal use?
A queue (FIFO): children join at the rear, so each level is finished before the next level starts.
A balanced BST has 1,000,000 nodes. About how many comparisons does a search need at most?
The height of a balanced tree is about log₂ n, and log₂ 1,000,000 ≈ 20. Each comparison skips half of what is left.
Trees quiz
Test yourself: 5 questions, 70% to pass. Create a free account to take the quiz, save your progress and work towards the certificate.