A tree organises data in a hierarchy — one root at the top, branching down to leaves at the bottom.
Unlike arrays and linked lists where every element has exactly one predecessor, a tree node can have multiple children.
This hierarchical structure makes trees the natural choice for representing file systems, organisational charts, XML documents, and — most importantly in algorithms — for achieving O(log n) search, insert, and delete through a Binary Search Tree.
Foundations
Tree Terminology
Before studying BSTs and AVL trees, it is essential to understand the vocabulary. Every concept in tree algorithms refers to these terms.
🌳
Root
The topmost node with no parent. Every tree has exactly one root. All paths in the tree originate from the root.
🍃
Leaf
A node with no children. Leaves are at the bottom of the tree. In the diagram above, 20, 40, 60, and 80 are all leaves.
📏
Height
The length of the longest path from the root to any leaf, measured in edges. The tree above has height 2. Height determines worst-case search time.
📐
Depth
The distance from the root to a given node. The root has depth 0. Node 30 has depth 1. Nodes 20, 40, 60, 80 have depth 2.
👨👧👦
Parent and Child
Node A is the parent of node B if there is a direct edge from A to B pointing downward. B is then a child of A. A node can have multiple children but only one parent.
🌿
Subtree
Any node and all its descendants form a subtree. Node 30 is the root of a subtree containing 20 and 40. This recursive structure is the basis of tree algorithms.
Binary Search Tree
BST — The Ordered Binary Tree
A Binary Search Tree is a binary tree with one additional rule called the BST property: for every node, all values in its left subtree are smaller and all values in its right subtree are larger. This single constraint enables O(log n) search — the same principle as binary search on a sorted array, but in a dynamic tree structure that supports efficient insert and delete.
Search in a BST: To search for value 60 — start at root 50. 60 > 50 → go right to 70. 60 < 70 → go left to 60. Found! Only 3 comparisons for 7 nodes. Each comparison eliminates half the remaining tree — this is O(log n) average case.
The three core BST operations — search, insert, and delete — all follow the same principle: compare the target value with the current node, then recurse left or right.
// BST Search (recursive)function search(node, target):
if node == NULL: return NULL // not foundif target == node.data: return node // foundif target < node.data:
return search(node.left, target) // go leftelse:
return search(node.right, target) // go right
The degenerate BST problem: If values are inserted in sorted order (1, 2, 3, 4, 5…), the BST degenerates into a linked list — every node has only a right child. Height becomes n and search is O(n), losing all advantage. This is exactly why AVL trees were invented.
Tree Traversals
In-order · Pre-order · Post-order
A traversal visits every node in the tree exactly once. The order in which the current node is visited relative to its left and right subtrees defines three distinct traversal types. Each produces a different sequence and serves a different purpose.
⬅️➡️
In-order (Left → Root → Right)
Visits the left subtree, then the root, then the right subtree. For a BST, in-order traversal always produces a sorted sequence. This is the most important traversal for BSTs.
20
→
30
→
40
→
50
→
60
→
70
→
80
🔼⬅️➡️
Pre-order (Root → Left → Right)
Visits the root first, then recursively traverses left and right subtrees. Used to copy or serialise a tree — the root must be known before its children to reconstruct the tree.
50
→
30
→
20
→
40
→
70
→
60
→
80
⬅️➡️🔽
Post-order (Left → Right → Root)
Visits both subtrees before the root. Used to delete a tree (children must be freed before their parent) and to evaluate expression trees.
20
→
40
→
30
→
60
→
80
→
70
→
50
Self-Balancing Trees
AVL Tree — Guaranteed O(log n)
An AVL tree is a BST with an automatic balancing rule: for every node, the heights of its left and right subtrees may differ by at most 1. This difference is called the balance factor. If any insertion or deletion causes a balance factor to become +2 or −2, the tree immediately performs a rotation to restore balance. This guarantees the tree height never exceeds 1.44 log₂(n) — ensuring O(log n) search, insert, and delete in the worst case, always.
BF = 0: perfectly balanced at this node BF = +1: left is one level taller — acceptable BF = −1: right is one level taller — acceptable BF = +2 or −2: violation — rotation required immediately
🔄
Four Rotation Types
LL Rotation: inserted into left subtree of left child → single right rotation
RR Rotation: inserted into right subtree of right child → single left rotation
LR Rotation: inserted into right subtree of left child → left rotation then right rotation
RL Rotation: inserted into left subtree of right child → right rotation then left rotation
Balanced AVL tree — balance factors shown in green (BF = height(L) − height(R))
Why AVL over BST? A plain BST guarantees O(log n) only on average — the worst case is O(n) for a degenerate tree. An AVL tree guarantees O(log n) in every case by maintaining balance after every operation. The cost is slightly slower insertions and deletions (due to rotation overhead), but the guarantee of balanced height is worth it for applications where worst-case performance must be predictable.
Performance
Time Complexity Comparison
Operation
BST (Average)
BST (Worst)
AVL Tree (Always)
Search
O(log n)
O(n)
O(log n)
Insert
O(log n)
O(n)
O(log n)
Delete
O(log n)
O(n)
O(log n)
In-order traversal
O(n)
O(n)
O(n)
Height
O(log n) average
O(n) worst
O(log n) guaranteed
Space
O(n)
O(n)
O(n)
Applications
Where Trees Are Used
🗂️
File Systems
Every file system is a tree. The root directory is the root node; subdirectories are internal nodes; files are leaves. Navigating a path like /home/vivek/documents is a top-down tree traversal — one directory node per level.
🗄️
Database Indexing (B-Trees)
Database engines (MySQL, PostgreSQL) use B-trees and B+ trees — generalisations of BSTs that can have many children per node — to index table columns. This allows O(log n) lookup in tables with millions of rows.
🖥️
Expression Trees
Compilers represent arithmetic expressions as trees. The operator is the root; operands are children. Post-order traversal of the tree evaluates the expression. This is how Python and Java compilers parse and evaluate code.
🔡
Auto-complete and Dictionaries
Trie trees (prefix trees) store strings character by character — each edge represents a character, each path from root to a node represents a prefix. Searching for all words starting with "comp" is a subtree traversal, making tries ideal for search suggestions.
Interactive Learning
BST Quest and AVL Tree Quest
BST Quest lets you insert, delete, and search on a live tree with animated traversals. AVL Tree Quest shows balance factors on every node and animates LL, RR, LR, and RL rotations as they occur during insertion.