The node structure
A binary tree node has a value and two child pointers — left and right.
Either child can be NULL. A node with no children is a leaf.
The topmost node is the root.
typedef struct Node {
int val;
struct Node *left;
struct Node *right;
} Node;
int height(Node *n) {
if (!n) return 0;
int lh = height(n->left);
int rh = height(n->right);
return 1 + (lh > rh ? lh : rh);
}
The three traversal orders
How you visit the nodes determines what order you see the values.
There are three recursive orders, each with distinct uses:
// in-order: left → node → right
// visits BST nodes in sorted order
void inorder(Node *n) {
if (!n) return;
inorder(n->left);
visit(n);
inorder(n->right);
}
// pre-order: node → left → right
// visits root before subtrees — good for copying/serializing
void preorder(Node *n) {
if (!n) return;
visit(n);
preorder(n->left);
preorder(n->right);
}
// post-order: left → right → node
// visits children before parent — good for freeing a tree
void postorder(Node *n) {
if (!n) return;
postorder(n->left);
postorder(n->right);
visit(n);
}
💡
Free a tree with post-order traversal.
If you free a node before freeing its children, you lose the pointers to the children.
Post-order visits children first, so free(n) at the visit step
is always safe — both subtrees are already gone.
Height and balance
A perfectly balanced binary tree of n nodes has height ⌊log₂(n)⌋.
An unbalanced tree — where most nodes chain to one side — has height up to n,
degenerating into a linked list. Balance matters because tree operations
cost O(height): O(log n) balanced, O(n) degenerate.
Building a tree in C
Each node is heap-allocated. You malloc a node, set its value,
set both children to NULL, then connect it to the tree by assigning it
to the parent's left or right pointer.
Node *make_node(int val) {
Node *n = malloc(sizeof(Node));
n->val = val;
n->left = NULL;
n->right = NULL;
return n;
}
// free all nodes with post-order traversal
void free_tree(Node *n) {
if (!n) return;
free_tree(n->left);
free_tree(n->right);
free(n);
}
⚠️
Memory ownership in trees is manual.
Every make_node allocates. A traversal that loses the pointer to a subtree
before freeing it leaks that entire subtree. Always free trees with post-order
traversal before discarding the root pointer.
Level-order (BFS) traversal
The three recursive traversals go deep first. Level-order visits nodes
row by row — root, then all depth-1 nodes, then all depth-2 nodes, and so on.
It requires a queue, not just recursion.
// level-order using an explicit queue
void level_order(Node *root) {
if (!root) return;
Node *q[1024];
int head = 0, tail = 0;
q[tail++] = root;
while (head < tail) {
Node *n = q[head++];
visit(n);
if (n->left) q[tail++] = n->left;
if (n->right) q[tail++] = n->right;
}
}
💡
BFS on trees is just level-order.
The level-order pattern (enqueue root, process node, enqueue children) is the tree
form of breadth-first search. You'll see the same structure again when searching graphs
in lesson 14.
one-line takeaway
A binary tree's cost is O(height) — O(log n) when balanced, O(n) when it degenerates to a list.