Difficulty: Intermediate | Prerequisites: Linked memory, pointers, recursion, Big-O notation
Trees are the first non-linear data structure in the course and one of the most important. Binary search trees give you O(log n) search, insert, and delete when they are balanced, but degrade to O(n) when they are not. AVL trees fix this problem by enforcing a balance condition after every operation. This block of material is heavily tested and forms the basis for B-trees, heaps, and graph algorithms later in the course. If you are comfortable with recursion, trees will feel natural; if not, this is the topic that will force you to get comfortable.
TL;DR: Binary trees store data in nodes with at most two children. Binary search trees add an ordering property (left < node < right) for efficient lookup. AVL trees maintain balance through rotations so that all operations stay O(log n).
Binary tree
A tree where each node has at most two children, referred to as left and right. In simple terms, every node branches into at most two directions.
Full binary tree
Every node has either 0 or 2 children. No node has exactly one child.
Complete binary tree
Every level is fully filled except possibly the last, which is filled from left to right. This is the shape property used by heaps.
Perfect binary tree
Every internal node has exactly two children and all leaves are at the same depth. A perfect binary tree with height h has 2^(h+1) - 1 nodes.
Binary Search Tree (BST)
A binary tree where, for every node, all values in the left subtree are less than the node's value and all values in the right subtree are greater. This ordering enables O(log n) search in the average case.
In-order traversal
Visit left subtree, then the node, then right subtree. On a BST, this visits nodes in sorted order.
Pre-order traversal
Visit the node first, then left subtree, then right subtree. Useful for copying a tree or serialising its structure.
Post-order traversal
Visit left subtree, then right subtree, then the node. Useful for deleting a tree (children before parent).
Level-order traversal
Visit nodes level by level, left to right, using a queue. Also called breadth-first traversal.
In-order predecessor (IOP)
The largest value in the left subtree. Found by going left once, then right as far as possible. Used during BST deletion of a node with two children.
In-order successor (IOS)
The smallest value in the right subtree. Found by going right once, then left as far as possible. An alternative to IOP for two-child deletion.
Height of a tree
The number of edges on the longest path from the root to a leaf. A single node has height 0. An empty tree has height -1.
Balance factor
For a node in an AVL tree: height(right subtree) - height(left subtree). A node is balanced if its balance factor is -1, 0, or 1.
AVL tree
A self-balancing BST where the balance factor of every node is -1, 0, or 1. Named after Adelson-Velsky and Landis. Insertions and deletions that violate the balance condition are fixed by rotations.
Rotation
A local restructuring operation that restores balance. There are four cases: left rotation, right rotation, left-right rotation, and right-left rotation.
A binary tree with n nodes has exactly n - 1 edges
Maximum nodes at depth d: 2^d
Maximum total nodes with height h: 2^(h+1) - 1
Minimum height for n nodes: floor(log₂ n)
Maximum height for n nodes: n - 1 (degenerate/skewed tree)
In-order (LNR): produces sorted output on a BST
Recursive: traverse left, process node, traverse right
Iterative: use a stack, push left children until null, pop and process, move to right child
Pre-order (NLR): root is always the first element visited
Useful for creating a copy of the tree
Pre-order + in-order together uniquely define a binary tree
Post-order (LRN): root is always the last element visited
Used for safe deletion: delete children before parent
Used for evaluating expression trees
Level-order: uses a queue
Enqueue root, then repeatedly dequeue a node, process it, and enqueue its children
Find: compare target with current node; go left if smaller, right if larger; O(h) where h is the height
Insert: follow the find path until you reach a null pointer; create a new node there; O(h)
Remove: three cases
Node is a leaf: simply remove it
Node has one child: replace the node with its child
Node has two children: replace the node's value with its in-order predecessor (or successor), then recursively delete the IOP/IOS node (which will have at most one child)
All operations are O(h)
Best case: balanced tree, h = O(log n)
Worst case: degenerate tree (all nodes in a line), h = O(n)
Random insertions produce an expected height of O(log n), but adversarial or sorted input produces O(n)
A BST is only efficient when balanced. AVL trees enforce balance automatically.
After every insert or delete, check the balance factor of each ancestor of the modified node
If any node has a balance factor outside {-1, 0, 1}, perform rotations to restore balance
Case 1: Left-Left (LL) – right rotation
The imbalance is in the left child's left subtree
Perform a single right rotation at the unbalanced node
The left child becomes the new root of the subtree
Case 2: Right-Right (RR) – left rotation
Mirror of LL
The right child becomes the new root of the subtree
Case 3: Left-Right (LR) – left rotation then right rotation
The imbalance is in the left child's right subtree
First, left-rotate the left child
Then, right-rotate the unbalanced node
Case 4: Right-Left (RL) – right rotation then left rotation
Mirror of LR
First, right-rotate the right child
Then, left-rotate the unbalanced node
Find the first unbalanced ancestor (balance factor is +2 or -2)
Look at the direction of the imbalance:
Balance factor -2 → left-heavy → the problem is in the left subtree
Balance factor +2 → right-heavy → the problem is in the right subtree
Then check the child's balance factor:
Same sign as parent → single rotation (LL or RR)
Opposite sign → double rotation (LR or RL)
Insert as in a standard BST
Walk back up to the root, updating heights
At the first unbalanced node, determine the rotation case and apply it
A single insertion requires at most one rotation (single or double) to restore balance
Delete as in a standard BST (using IOP or IOS for two-child case)
Walk back up to the root, updating heights
At each unbalanced node, apply the appropriate rotation
Unlike insertion, deletion may require rotations at multiple ancestors (up to O(log n) rotations)
Minimum nodes in an AVL tree of height h:
N(h) = N(h-1) + N(h-2) + 1
With base cases N(0) = 1, N(1) = 2. This is similar to the Fibonacci sequence. It means the maximum height of an AVL tree with n nodes is approximately 1.44 log₂(n).
BST node count and height:
Perfect binary tree: n = 2^(h+1) - 1
Minimum height: h = floor(log₂ n)
Right rotation pseudocode:
rightRotate(node):
newRoot = node.left
node.left = newRoot.right
newRoot.right = node
update heights of node, then newRoot
return newRoot
Databases use balanced search trees (often B-trees, which extend these ideas) to index records for fast lookup. File systems use tree structures to organise directories. AVL trees are used in memory-constrained systems where the stricter balance guarantee (compared to red-black trees) reduces the worst-case lookup depth.
"BST operations are always O(log n)." Only when the tree is balanced. A BST built from sorted input degenerates into a linked list with O(n) operations.
"In-order predecessor is always a leaf." The IOP has no right child, but it may have a left child. It is not necessarily a leaf.
"AVL rotations change the in-order sequence." They do not. Rotations restructure the tree but preserve the BST ordering property. The in-order traversal produces the same sorted sequence before and after rotation.
"A single rotation always fixes an AVL tree after deletion." Insertion needs at most one rotation, but deletion can require rotations at every level back to the root.
⚠️ You will almost certainly be asked to insert and delete from a BST and trace through the process step by step.
⚠️ Know all four AVL rotation cases by heart. Be able to identify the case from a diagram and draw the result.
⚠️ Be ready to compute balance factors for every node in a tree.
⚠️ Understand the difference between height and depth (height is measured from the bottom, depth from the top).
⚠️ The relationship between tree traversals and unique tree reconstruction (pre-order + in-order, or post-order + in-order, uniquely define a tree) is a common exam topic.
True or false: A BST with n nodes always has height O(log n).
Fill in the blank: In-order traversal of a BST visits nodes in ______ order.
True or false: An AVL tree's balance factor can be -2.
Fill in the blank: To delete a BST node with two children, replace its value with the ______ and then delete that replacement node.
True or false: A left-right (LR) imbalance is fixed with a single rotation.
Answers: 1. False (worst case O(n)). 2. Sorted (ascending). 3. False (must be -1, 0, or 1; -2 triggers a rotation). 4. In-order predecessor (or in-order successor). 5. False (requires a double rotation: left then right).
Q: Insert the values 4, 2, 6, 1, 3, 5, 7 into an initially empty BST. What does the resulting tree look like? Is it balanced?
A: 4 becomes the root. 2 goes left, 6 goes right. 1 goes left of 2, 3 goes right of 2. 5 goes left of 6, 7 goes right of 6. The tree is a perfect binary tree of height 2 and is balanced.
Q: Insert 1, 2, 3 into an empty AVL tree. Show the tree after each insertion, including any rotations.
A: After inserting 1: tree is just [1]. After inserting 2: [1] with right child [2], balanced. After inserting 3: [1] has balance factor +2 (right-right case). Perform a left rotation: [2] becomes root, [1] is left child, [3] is right child.
Q: What is the maximum number of nodes in a binary tree of height 4?
A: 2^(4+1) - 1 = 31.
Q: Given a BST, deleting a node with two children using the in-order predecessor. Explain why the IOP has at most one child.
A: The IOP is the rightmost node in the left subtree. If it had a right child, that right child would be larger and therefore closer to the deleted node's value, making it the actual IOP. This is a contradiction, so the IOP cannot have a right child. It may have a left child.
AVL trees lead directly into B-trees (Week 6), which generalise the idea of balanced search trees for disk-based storage. The rotation concept reappears in other balanced tree variants (red-black trees, splay trees). Tree traversals are a special case of graph traversals (Week 10). Heaps (Week 7) use the complete binary tree shape but with a different ordering property.
binary tree, BST, binary search tree, AVL tree, Adelson-Velsky Landis, tree traversal, in-order, pre-order, post-order, level-order, breadth-first, tree rotation, left rotation, right rotation, left-right rotation, right-left rotation, balance factor, height, depth, full binary tree, complete binary tree, perfect binary tree, in-order predecessor, in-order successor, IOP, IOS, self-balancing tree, CS 225, data structures, UIUC