UNIT 11Prerequisite: Unit 05 — Linked Lists90 min read
Every data structure we have covered so far has been linear — arrays, linked lists, stacks, queues all store items in a straight sequence. Trees are different. They store data in a hierarchy — parent–child relationships where one node can connect to multiple others. This single change opens up an entirely new class of problems and solutions.
In this unit we build binary trees from scratch in C, learn all the vocabulary, implement every traversal, and understand the properties that make trees the backbone of some of the most important systems in computing.
// Section 1
What is a Tree?
A tree is a collection of nodes connected by edges, arranged so that there is exactly one path between any two nodes and no cycles. It looks like a real tree — but drawn upside down with the root at the top and the leaves at the bottom.
🏢 Think of a company org chart
The CEO is at the top. Under the CEO are VPs. Under each VP are managers. Under each manager are engineers. This hierarchy is exactly a tree. The CEO is the root. Engineers with no subordinates are leaves.
Root (CEO) — top of tree, no parent Internal nodes — have parent and children Leaves — no children, bottom of tree // Section 2
Tree Terminology — Words You Must Know
Trees have a vocabulary that everyone uses — in interviews, textbooks, and code reviews. Learn these terms once. You will use them forever.
| Term | Definition | In the org chart example |
|---|
| Root | The topmost node — has no parent | CEO |
| Node | Any single element in the tree | Any person in the chart |
| Edge | The connection between a parent and child | The line between CEO and VP |
| Parent | The node directly above another node | VP1 is parent of M1 |
| Child | A node directly below another node | M1 and M2 are children of VP1 |
| Leaf | A node with no children | E1, E2, E3, M3 |
| Height | Longest path from root to any leaf (in edges) | CEO → VP1 → M1 → E1 = height 3 |
| Depth | Distance from root to a specific node | M1 has depth 2 |
| Level | All nodes at the same depth | VP1 and VP2 are at level 1 |
| Subtree | Any node and all its descendants | VP1 + all below it = a subtree |
// Section 3
Binary Tree — At Most Two Children
A binary tree is a tree where every node has at most two children — called the left child and the right child. This constraint makes binary trees the most studied and most useful type of tree in computer science. Binary search trees, heaps, expression trees — all are binary trees.
Full Binary Tree
Every node has either 0 or 2 children. No node has exactly 1 child.
Complete Binary Tree
All levels are fully filled except possibly the last, which fills left to right.
Perfect Binary Tree
All internal nodes have exactly 2 children and all leaves are at the same level.
Degenerate Tree
Every parent has only one child — essentially becomes a linked list. Worst case for BST.
// Section 4
Binary Tree in C — Node Structure
A binary tree node is just like a linked list node — but with two next pointers instead of one. A left pointer and a right pointer. Both are NULL for leaf nodes.
#include <stdio.h>
#include <stdlib.h>
struct TreeNode {
int data;
struct TreeNode *left; /* pointer to left child */
struct TreeNode *right; /* pointer to right child */
};
typedef struct TreeNode TreeNode;
/* create a new node with given value */
TreeNode* createNode(int value) {
TreeNode *node = (TreeNode*)malloc(sizeof(TreeNode));
node->data = value;
node->left = NULL; /* no left child yet */
node->right = NULL; /* no right child yet */
return node;
}
int main() {
/* build this tree manually:
1
/ \
2 3
/ \
4 5
*/
TreeNode *root = createNode(1);
root->left = createNode(2);
root->right = createNode(3);
root->left->left = createNode(4);
root->left->right = createNode(5);
/* access nodes */
printf("Root: %d\n", root->data); /* 1 */
printf("Left child: %d\n", root->left->data); /* 2 */
printf("Right child: %d\n", root->right->data); /* 3 */
printf("Left->Left: %d\n", root->left->left->data); /* 4 */
return 0;
}
// How node 2 looks in memory — data + two pointers
Each node = 12 bytes on a 64-bit system: 4 (int) + 4 (padding) + 8 (left ptr) + 8 (right ptr)
// Section 5
Tree Traversals — Four Ways to Visit Every Node
With a linked list, there is only one way to traverse: start at head and follow next. With a tree, you have choices. The order in which you visit nodes produces completely different sequences — each useful for different problems. There are four standard traversals. Three use recursion (DFS), one uses a queue (BFS).
// We will use this tree for all four traversal examples
Inorder
Left → Root → Right
4 2 5 1 6 3 7
Use: BST sorted output
Preorder
Root → Left → Right
1 2 4 5 3 6 7
Use: Copy / serialize tree
Postorder
Left → Right → Root
4 5 2 6 7 3 1
Use: Delete tree, evaluate expressions
Level Order
Level by level (BFS)
1 2 3 4 5 6 7
Use: Shortest path, level problems
// Section 6
Inorder Traversal — Left, Root, Right
Inorder visits the left subtree first, then the root, then the right subtree. On a Binary Search Tree, inorder traversal always produces a sorted sequence — this is one of the most important tree properties you will use.
// Tracing inorder on our tree — follow Left → Root → Right at every node
inorder(1) → go left first
inorder(2) → go left first
inorder(4) → no left → print 4 → no right → return
→ print 2 → go right
inorder(5) → no left → print 5 → no right → return
→ print 1 → go right
inorder(3) → go left first
inorder(6) → no left → print 6 → no right → return
→ print 3 → go right
inorder(7) → no left → print 7 → no right → return
Result: 4 2 5 1 6 3 7
void inorder(TreeNode *root) {
if (root == NULL) return; /* base case: empty subtree */
inorder(root->left); /* 1. visit left subtree */
printf("%d ", root->data); /* 2. print current node */
inorder(root->right); /* 3. visit right subtree */
}
/* inorder(root) → prints: 4 2 5 1 6 3 7 */
Time:O(n)(every node visited exactly once)
Space:O(h)(h = height, call stack depth)
// Section 7
Preorder Traversal — Root, Left, Right
Preorder visits the root first, then the left subtree, then the right subtree. Because you always process the current node before going deeper, preorder is used to copy or serialize a tree — the output can be used to reconstruct the exact same tree.
void preorder(TreeNode *root) {
if (root == NULL) return;
printf("%d ", root->data); /* 1. print current node FIRST */
preorder(root->left); /* 2. visit left subtree */
preorder(root->right); /* 3. visit right subtree */
}
/* preorder(root) → prints: 1 2 4 5 3 6 7 */
💡 Note
Real use of preorder: When you save a file system to disk, the folder structure is written in preorder — the folder itself is saved before its contents. When you load it back, you recreate each folder before adding its children. That is preorder traversal in a real system.
// Section 8
Postorder Traversal — Left, Right, Root
Postorder visits the left subtree, then right subtree, and processes the root last. Because you handle all children before the parent, postorder is the natural order for deleting a tree (free children before freeing parent) and evaluating expression trees (compute sub-expressions before applying the operator).
void postorder(TreeNode *root) {
if (root == NULL) return;
postorder(root->left); /* 1. visit left subtree */
postorder(root->right); /* 2. visit right subtree */
printf("%d ", root->data); /* 3. print current node LAST */
}
/* postorder(root) → prints: 4 5 2 6 7 3 1 */
/* deleting a tree safely — must use postorder */
void deleteTree(TreeNode *root) {
if (root == NULL) return;
deleteTree(root->left); /* free children first */
deleteTree(root->right);
free(root); /* then free the parent */
}
// Section 9
Level Order Traversal — BFS with a Queue
Level order visits nodes level by level — all nodes at depth 0 first (root), then all at depth 1, then depth 2, and so on. This is Breadth-First Search (BFS) on a tree. Unlike the other three traversals which use recursion and the call stack, level order needs an explicit queue to track which nodes to visit next.
// Visit level by level — breadth first
Full output: 1 2 3 4 5 6 7
#include <stdio.h>
#include <stdlib.h>
/* simple queue using array for level order */
#define QMAX 100
void levelOrder(TreeNode *root) {
if (root == NULL) return;
TreeNode *queue[QMAX];
int front = 0, rear = 0;
queue[rear++] = root; /* enqueue root */
while (front < rear) {
TreeNode *current = queue[front++]; /* dequeue */
printf("%d ", current->data); /* visit current node */
/* enqueue left child if it exists */
if (current->left != NULL) {
queue[rear++] = current->left;
}
/* enqueue right child if it exists */
if (current->right != NULL) {
queue[rear++] = current->right;
}
}
}
/* levelOrder(root) → prints: 1 2 3 4 5 6 7 */
🎯 Pro Tip
Why a queue? When we dequeue a node and process it, we enqueue its children. Children go to the back of the queue — so all siblings at the current level are processed before going deeper. This naturally produces level-by-level order. This exact pattern — queue-based BFS — is used in graph traversal in Unit 15.
// Section 10
Height of a Tree and Counting Nodes
Two of the most common tree problems in interviews. Both use recursion naturally — because the height of a tree depends on the height of its subtrees, and the count of nodes is 1 plus the count of the left subtree plus the right.
/* Height = longest path from root to any leaf (measured in edges) */
int height(TreeNode *root) {
if (root == NULL) return -1; /* empty tree has height -1 */
/* (use 0 if measuring in nodes, -1 if measuring in edges) */
int leftHeight = height(root->left);
int rightHeight = height(root->right);
/* height = 1 + the taller of the two subtrees */
int taller = leftHeight > rightHeight ? leftHeight : rightHeight;
return 1 + taller;
}
/* Count = total number of nodes in the tree */
int countNodes(TreeNode *root) {
if (root == NULL) return 0; /* empty tree has 0 nodes */
return 1 + countNodes(root->left) + countNodes(root->right);
/* 1 for current node + all nodes in left + all nodes in right */
}
/* Count only leaf nodes (nodes with no children) */
int countLeaves(TreeNode *root) {
if (root == NULL) return 0;
if (root->left == NULL && root->right == NULL) return 1; /* it is a leaf */
return countLeaves(root->left) + countLeaves(root->right);
}
int main() {
/* build our example tree */
TreeNode *root = createNode(1);
root->left = createNode(2);
root->right = createNode(3);
root->left->left = createNode(4);
root->left->right = createNode(5);
root->right->left = createNode(6);
root->right->right = createNode(7);
printf("Height: %d\n", height(root)); /* 2 */
printf("Total nodes: %d\n", countNodes(root)); /* 7 */
printf("Leaf nodes: %d\n", countLeaves(root)); /* 4 */
return 0;
}
Tracing height(root=1):
height(1) = 1 + max(height(2), height(3))
height(2) = 1 + max(height(4), height(5))
height(4) = 1 + max(-1, -1) = 0
height(5) = 1 + max(-1, -1) = 0
height(2) = 1 + max(0, 0) = 1
height(3) = 1 + max(0, 0) = 1
height(1) = 1 + max(1, 1) = 2 ✓
// Section 11
Trees in the Real World
📁File systems
Every folder on your computer is a tree node. /home/asil/projects is a path from root to a node. ls -R is a preorder traversal.
🌐HTML / DOM
Every webpage is a tree. The html tag is the root, head and body are children, and every div, p, span is a node. JavaScript's querySelector walks this tree.
🧮Expression trees
The expression (3 + 4) × 2 is stored as a tree with × at root, 2 as right child, and + as left child with 3 and 4 as its children. Postorder evaluates it correctly.
🗄️Database indexes
MySQL and PostgreSQL use B-Trees (a generalisation of binary trees) for indexes. Every time you query with WHERE id = 5, a tree traversal finds it in O(log n).
🔤Auto-complete and spell check
The Trie data structure (Unit 19) is a tree where each path from root to leaf spells a word. Google's search suggestions use trie-based trees.
// Section 12
Errors You Will Hit
⚠ Not checking NULL before accessing node fields
Symptom: Segmentation fault when traversal tries to access root->left->data on a NULL pointer
Fix: Every recursive traversal function must start with: if (root == NULL) return. Never access a field without checking NULL first.
⚠ Freeing a parent before freeing children
Symptom: Memory leak — children become unreachable after parent is freed
Fix: Always use postorder to delete a tree — free left subtree, free right subtree, then free the current node.
⚠ Confusing height in edges vs height in nodes
Symptom: Height calculations off by 1
Fix: A single node has height 0 (in edges) or height 1 (in nodes). Be consistent. This unit uses edges — base case returns -1 for NULL.
// Quick Reference
All Traversals — Side by Side
| Traversal | Order | Output on example | Method | Key use |
|---|
| Inorder | Left → Root → Right | 4 2 5 1 6 3 7 | Recursion | Sorted output from BST |
| Preorder | Root → Left → Right | 1 2 4 5 3 6 7 | Recursion | Copy / serialize tree |
| Postorder | Left → Right → Root | 4 5 2 6 7 3 1 | Recursion | Delete tree, evaluate expressions |
| Level Order | Level by level | 1 2 3 4 5 6 7 | Queue (BFS) | Shortest path, level problems |
// What's Next
You Are Ready for Unit 12
You now understand trees completely — the terminology, the node structure in C, all four traversals with full traces, height, count, and how trees power real systems from file systems to databases.
In Unit 12 we cover the Binary Search Tree (BST) — a binary tree with one powerful rule: every left child is smaller than its parent, every right child is larger. This rule makes search, insert, and delete all run in O(log n) on a balanced tree. The BST is the gateway to understanding every advanced tree structure.
UP NEXT → UNIT 12
Binary Search Tree — O(log n) Everything
Insert, search, delete (3 cases), balanced vs unbalanced — in C.
🎯 Key Takeaways
- ✓A tree stores data in a hierarchy — parent-child relationships with no cycles
- ✓Binary tree: every node has at most 2 children — left and right
- ✓Each node in C has: data, *left pointer, *right pointer. Both are NULL for leaf nodes
- ✓Inorder (L → Root → R): produces sorted output on a BST — most important traversal
- ✓Preorder (Root → L → R): visits parent before children — used to copy or serialize trees
- ✓Postorder (L → R → Root): visits children before parent — used to delete trees safely
- ✓Level order: visits level by level using a queue (BFS) — gives shortest path in unweighted trees
- ✓Height = longest root-to-leaf path in edges. height(NULL) = -1. height(leaf) = 0
- ✓All traversals are O(n) time — every node visited exactly once
- ✓Trees power file systems (preorder), databases (B-trees), HTML (DOM), and compilers