Tree Data Structures: Binary Trees, BSTs, Heaps & Balanced Trees Guide
Trees are hierarchical data structures that organize information in parent-child relationships. They are fundamental to computer science — databases use B-trees for indexes, operating systems use trees for filesystem organization, compilers use abstract syntax trees for code representation, and networking uses spanning trees for routing. Understanding tree data structures is essential for any serious software engineer.
Binary Trees: The Foundation
A binary tree is a tree where each node has at most two children, conventionally called left and right. Binary trees form the basis of BSTs, heaps, expression trees, and Huffman coding trees.
Terminology
The root is the topmost node with no parent. A leaf is a node with no children. The height of a node is the number of edges on the longest path from that node to a leaf. The depth of a node is the number of edges from the root to that node. A full binary tree has every node with 0 or 2 children. A complete binary tree has all levels filled except possibly the last, which fills from left to right.
Tree Traversals
Traversals define the order in which nodes are visited. Each traversal serves different purposes:
In-order traversal (Left, Root, Right): For a BST, in-order produces sorted order. It visits nodes in ascending key order, making it useful for range queries and converting a BST to a sorted list.
Pre-order traversal (Root, Left, Right): Used to create a copy of a tree — create the root node first, then recursively copy the left and right subtrees. Prefix expression evaluation also uses pre-order.
Post-order traversal (Left, Right, Root): Used to delete a tree — children are deleted before their parent, ensuring no dangling pointers. Postfix expression evaluation (Reverse Polish Notation) uses post-order.
Level-order traversal (Breadth-first): Visits nodes level by level using a queue. It finds the shortest path in unweighted trees and is used in serialization formats.
def inorder(node):
if node:
inorder(node.left)
print(node.value)
inorder(node.right)
def level_order(root):
queue = [root]
while queue:
node = queue.pop(0)
print(node.value)
if node.left:
queue.append(node.left)
if node.right:
queue.append(node.right)Each traversal runs in O(n) time and O(h) space for the recursion stack (or explicit queue for level-order).
Binary Search Trees: Ordered Search
A BST maintains the invariant that for every node, all values in the left subtree are smaller and all values in the right subtree are larger. This property enables binary search within the tree structure.
Search, Insert, and Delete
Search: Compare the target with the root. If equal, return the node. If smaller, search the left subtree. If larger, search the right subtree. Each comparison eliminates one subtree. Complexity: O(h) where h is the tree height.
Insert: Search for the key. When the search reaches a null child, insert the new node at that position. No restructuring is needed. Complexity: O(h).
Delete: Three cases exist. If the node is a leaf, simply remove it. If it has one child, replace the node with its child. If it has two children, find the in-order successor (smallest node in the right subtree) or predecessor (largest node in the left subtree), copy its value, and recursively delete that node. Complexity: O(h).
Degeneration and Balancing
In the worst case, inserting sorted data into an unbalanced BST produces a degenerate tree — essentially a linked list with h = n. Search degrades to O(n). This is the primary weakness of basic BSTs.
Self-balancing trees solve this problem. AVL trees maintain a balance factor (height difference between left and right subtrees) of at most 1, using rotations to restore balance after insertions and deletions. AVL trees guarantee O(log n) operations but perform frequent rotations.
Red-Black trees maintain approximate balance through color properties: nodes are red or black, the root is black, red nodes have black children, and every path from root to leaf has the same number of black nodes. Red-Black trees allow greater imbalance than AVL trees but require fewer rotations, making them preferable for write-heavy workloads. C++ std::map and Java TreeMap use Red-Black trees.
Heaps: The Priority Data Structure
A heap is a complete binary tree that satisfies the heap property. In a max-heap, every parent is greater than or equal to its children — the maximum element is always at the root. In a min-heap, every parent is less than or equal to its children.
Heap Operations
Insert: Add the new element at the end of the heap (first available position in level-order) and bubble it up by swapping with its parent until the heap property is restored. O(log n).
Extract Max/Min: Remove the root, replace it with the last element, and bubble it down by swapping with the larger child (max-heap) or smaller child (min-heap). O(log n).
Build Heap: Convert an array to a heap using Floyd’s algorithm: starting from the last non-leaf node, bubble down each node. O(n) — a surprising and elegant result.
Applications
Heaps power priority queues, used in Dijkstra’s shortest path algorithm (min-heap), Heap Sort (max-heap), and task scheduling (both variants). The median maintenance problem — keeping track of the median in a stream of numbers — uses two heaps: a max-heap for the lower half and a min-heap for the upper half.
Tries: Prefix Trees
A trie stores strings character by character. Each node represents a character, and paths from root to leaf represent strings (or to marked nodes for prefix matching). Insertion and lookup are O(m) where m is the string length, independent of the number of strings stored.
Tries are memory-intensive in their basic form — each node contains an array of 26 (or 256) pointers. Compressed tries (radix trees, Patricia tries) merge single-child nodes to save space. The Linux kernel uses the radix tree for page cache management.
Balanced Trees in Practice
B-trees generalize binary search trees by allowing multiple keys per node. A B-tree of order m has at most m children per node. Databases like PostgreSQL and MySQL use B+ trees (a B-tree variant with all data in leaves, linked for sequential access) for indexes. B-trees are optimized for block-oriented storage — each node fits in a disk page, minimizing I/O operations.
Frequently Asked Questions
What is the difference between a binary tree and a binary search tree?
A binary tree has no ordering constraint — any value can be at any node. A binary search tree maintains the BST invariant: left values < root < right values. BSTs support efficient search (O(log n) when balanced); binary trees without ordering require O(n) search.
Why are heaps used for priority queues instead of BSTs?
Heaps provide O(1) access to the maximum or minimum element, while BSTs require O(log n) to find the extremum. Heaps are also more memory-efficient — they are stored in a flat array using the complete binary tree property, eliminating child pointers.
How do AVL trees differ from Red-Black trees?
Both are self-balancing BSTs with O(log n) operations. AVL trees enforce stricter balance (height difference ≤ 1), providing faster lookups but more rotations during insertions and deletions. Red-Black trees allow greater imbalance, reducing rotation frequency. For lookup-heavy workloads, prefer AVL. For write-heavy workloads, prefer Red-Black.
What is the height of a perfectly balanced binary tree with n nodes?
The minimum height of a binary tree with n nodes is ⌊log₂(n)⌋. A perfectly balanced tree with 1,000,000 nodes has height approximately 20 — enabling very fast search, insertion, and deletion.
When should I use a trie versus a BST for string storage?
Use a trie for prefix queries (autocomplete, spell-check), O(m) worst-case lookup regardless of set size, and when shared prefixes save memory. Use a BST (balanced) when memory is constrained, when range queries over string order are needed, or when the character alphabet is very large.
Advanced Tree Variants
Segment Trees
Segment trees support range queries and point updates on arrays in O(log n) time. Each node represents a segment of the array and stores aggregate information (sum, min, max, or custom operation). To query a range, the tree visits O(log n) nodes whose segments exactly partition the query range. Segment trees are essential in competitive programming and computational geometry.
Fenwick Trees (Binary Indexed Trees)
Fenwick trees provide O(log n) prefix sum queries and point updates with extremely low constant factors. They use a clever indexing scheme based on the least significant set bit. Fenwick trees are simpler and faster than segment trees for prefix-based queries but cannot directly handle arbitrary range queries without modification.
B-Trees
B-trees generalize BSTs with multiple keys per node (typically hundreds to thousands). Each internal node has between m/2 and m children. The high branching factor means B-trees are shallow even with billions of entries: a B-tree with order 1000 can store one billion keys with just three levels. B-trees are the standard index structure in relational databases — PostgreSQL, MySQL, SQLite, and Oracle all use B+ tree variants.