C Binary Trees & Recursive Search: BST, Tree Traversals & Balancing (Complete Guide)

C Binary Trees & Recursive Search: BST, Tree Traversals & Balancing (Complete Guide)

Table of Contents

• What Is a Binary Tree?
• The BST Property
• Node Structure and Creation
• Recursive Insertion
• Recursive Search: O(log n)
• Tree Traversal Orders
• Finding Min, Max, and Successor
• BST Deletion: The Hardest Operation
• Tree Height and Balance
• Memory Management: Freeing the Entire Tree
• Real-World Applications
• Frequently Asked Questions
• Key Takeaway

What Is a Binary Tree?

A binary tree is a linked data structure where each node has:

• A data value.
• A left child pointer (or NULL).
• A right child pointer (or NULL).

Unlike arrays (contiguous memory) or linked lists (linear chain), trees represent hierarchical relationships. The height of a balanced binary tree with n nodes is O(log n) — for 1 million nodes, the height is only ~20. This logarithmic depth is what makes tree operations so efficient.

Terminology:

• Root: The top node with no parent.
• Leaf: A node with no children (left = NULL and right = NULL).
• Height: The maximum number of edges from root to a leaf.
• Depth: The number of edges from the root to a specific node.
• Subtree: Any node viewed as the root of the sub-structure below it.

The BST Property

A Binary Search Tree maintains a critical invariant:

For every node N: all values in N's left subtree are less than N's value, and all values in N's right subtree are greater than N's value.

This property holds recursively for every node in the tree. It means:

• Searching: at each node, eliminate half the remaining tree.
• In-order traversal: produces values in sorted ascending order.
• Insert/search/delete: O(log n) for balanced trees, O(n) worst case when degenerate.

Node Structure and Creation

Recursive Insertion

Recursion is the natural idiom for tree operations. The recursive structure directly mirrors the tree's recursive structure:

Each recursive call either inserts into the left subtree or the right subtree, consuming one level of the tree per call. For a balanced tree with n nodes, this recurses at most log₂(n) times.

Recursive Search: O(log n)

Tree Traversal Orders

Three fundamental traversal orders, each with different applications:

Mnemonic: Position of "Root" in the traversal name tells you when the root is processed:

• Pre-order: Root is first (before children).
• In-order: Root is in the middle (between left and right).
• Post-order: Root is last (after children).

For a BST with values 70:

• In-order: 10 20 30 40 50 60 70 (sorted!)
• Pre-order: 50 30 20 10 40 70 60 (root first)
• Post-order:10 20 40 30 60 70 50 (leaves first)

Finding Min, Max, and Successor

These O(log n) operations (O(h) where h = tree height) are fundamental to:

• Database range queries: WHERE price >= 100 AND price <= 500 traverses from the minimum ≥ 100 to maximum ≤ 500 in-order.
• Deletion of nodes with two children: Replace with the in-order successor (minimum of right subtree).

BST Deletion: The Hardest Operation

Deletion has three cases:

1. Node is a leaf (no children): Simply remove it.
2. Node has one child: Replace the node with its child.
3. Node has two children: Replace with in-order successor, then delete the successor.

Tree Height and Balance

The degenerate BST problem: If you insert already-sorted values (1, 2, 3, 4, 5...) into a BST, every node goes to the right child, producing a linked list with O(n) search. Self-balancing trees solve this:

• AVL Tree: Maintains height balance factor within ±1 using rotations after each insert/delete.
• Red-Black Tree: Used in C++ STL std::map, Java TreeMap, Linux kernel's CFS scheduler. Relaxed balance (up to 2× height difference) for faster insertions.
• B-Tree: Used in databases (SQLite, PostgreSQL). Multi-way branching with large node capacities matching disk block sizes.

Memory Management: Freeing the Entire Tree

Always use post-order traversal to free a tree — you must free children before the parent:

Complete usage example:

Real-World Applications

Frequently Asked Questions

What is an "unbalanced" BST and why is it a problem? If you insert items in sorted order, each new item is always larger than the previous root and goes to the right child, creating a degenerate tree that looks like a linked list. Search degrades from O(log n) to O(n). Self-balancing trees (AVL, Red-Black) use rotations after each insert to maintain height balance.

How is a Red-Black tree different from an AVL tree? AVL trees maintain strict height balance (height difference ≤ 1), making lookups slightly faster but insertions slower (more rotations needed). Red-Black trees allow a more relaxed balance (longest path ≤ 2× shortest) but have fewer rotations on average, making insertions and deletions faster. Red-Black trees are preferred in most production systems.

Why do databases use B-Trees instead of BSTs? BSTs have 1 key per node — with millions of records, the tree can be 20+ levels deep, each level potentially requiring a disk read (millisecond latency). B-Trees have many keys per node (hundreds to thousands), reducing tree height to 3-5 levels. Each node is sized to fit exactly one disk block (4KB-16KB), maximizing I/O efficiency.

When should I use a recursive tree traversal vs an iterative one? Recursive traversals are cleaner code. The stack depth equals the tree height: for a balanced tree with 1M nodes, that's ~20 levels — perfectly safe. Iterative traversals (using an explicit stack) are preferred when: the tree might be degenerate (O(n) depth), you need to pause/resume traversal (iterator pattern), or you're working in a stack-constrained environment (embedded systems).

Key Takeaway

Binary Search Trees provide Logarithmic Performance for search, insertion, and deletion with the bonus of ordered data. This combination — which neither arrays nor hash tables provide — is what makes trees the backbone of database indexing, OS scheduling, and compiler construction.

By mastering tree node structure, recursive operations, and the three traversal orders, you gain a mental model that extends directly to B-Trees, Red-Black Trees, tries, and segment trees — the data structures powering the world's most critical software infrastructure.

Read next: Bitwise Operations & Low-Level I/O: Bit Manipulation in C →

Part of the C Mastery Course — 30 modules from C basics to expert systems engineering.