Trees and Graphs Guide — Data Structures and Algorithms
Trees and graphs are the most versatile data structures in computer science. They model hierarchies, networks, and relationships of all kinds — from file systems and database indexes to social networks and neural networks. Understanding trees and graphs is essential for solving complex problems in virtually every domain of software engineering, from operating systems to artificial intelligence.
A tree is a hierarchical data structure with a root node and child nodes, where each node has exactly one parent except the root. Trees model hierarchical relationships like organizational charts, file system directories, XML and JSON document structure, decision trees in machine learning, and abstract syntax trees in compilers. A graph generalizes the tree by allowing any node to connect to any other node, modeling networks without hierarchical constraints like social networks, transportation systems, communication networks, and dependency graphs.
Trees
Trees are a special case of graphs with no cycles and a single root node. They provide efficient access patterns for hierarchical data and sorted collections. The absence of cycles means there is exactly one path between any two nodes in a tree, simplifying algorithms like search and traversal.
Binary Tree
Each node in a binary tree has at most two children, referred to as left and right. Binary trees are the foundation for more specialized structures including binary search trees for sorted data, heaps for priority queues, expression trees for compiler parsing, and Huffman coding trees for data compression. Their simplicity makes them the most studied and implemented tree structure in computer science.
Binary Search Tree
A BST maintains the ordering property that for any node, all values in the left subtree are less than the node’s value, and all values in the right subtree are greater. This property enables efficient search by comparing the target to each node’s value and recursing into the appropriate subtree — essentially performing binary search on a dynamic data structure. In a balanced BST, search, insertion, and deletion are all O(log n). However, an unbalanced BST can degenerate into a linked list with O(n) operations if elements are inserted in sorted order without rebalancing.
Tree Traversals
Three standard traversal orders serve different purposes. Inorder traversal visits left subtree, then root, then right subtree, producing elements in sorted order for a BST. Preorder traversal visits root, then left, then right, useful for creating a copy of the tree or serializing it for storage and transmission. Postorder traversal visits left, then right, then root, used for deleting a tree from memory and evaluating expression trees where children must be processed before their parent.
Balanced Trees
BSTs can become unbalanced when elements are inserted in sorted order or other pathological patterns. Balanced trees automatically correct imbalance through rotation operations that restructure the tree while preserving the BST ordering property.
AVL trees maintain a strict balance condition where the height difference between left and right subtrees never exceeds 1. After every insertion or deletion, the tree checks for violations and performs single or double rotations to restore balance. AVL trees provide faster lookups than Red-Black trees due to stricter balance, at the cost of more rotations during insertions and deletions. Red-Black trees use a color-based balancing scheme where each node is either red or black, with constraints preventing consecutive red nodes and ensuring balanced black height. They provide faster insertions and deletions than AVL trees with slightly slower lookups. Red-Black trees are used in Java’s TreeMap, C++’s std::map, and Linux’s completely fair scheduler.
B-Trees generalize binary search trees by allowing many children per node, optimized for block-based storage systems. They are the standard index structure in relational databases including PostgreSQL, MySQL, and SQLite. Each node in a B-tree can hold hundreds of keys, and the tree height stays very shallow even for millions of records — a B-tree with a fanout of 500 can store 125 million records at height 3.
Graphs
A graph G equals a set of vertices V and a set of edges E connecting pairs of vertices. Graphs can be directed where edges have a direction from source to target, or undirected where edges are bidirectional. Edges can also have weights representing costs, distances, or capacities.
Representations
The adjacency list representation stores each vertex along with its list of neighboring vertices. This is the most common representation for sparse graphs where each vertex connects to only a small fraction of all possible vertices, using O(V+E) space and providing fast neighbor iteration for traversal algorithms. The adjacency matrix representation uses a 2D array indexed by vertex pairs, using O(V squared) space but providing O(1) edge existence checks, making it suitable for dense graphs.
Graph Traversal
DFS explores as far as possible along each branch before backtracking, using a stack or recursion. It uses less memory than BFS for deep graphs and is preferred for topological sorting, cycle detection, and exhaustive search problems. BFS explores level by level using a queue, finding the shortest path in unweighted graphs. It is preferred for social network degree-of-separation analysis, web crawling within a fixed distance, and finding connected components.
Binary Tree Properties and Analysis
Several important properties guide the analysis and use of binary trees. The height of a perfect binary tree with n nodes is log base 2 of n. The number of leaf nodes in a full binary tree is one more than the number of internal nodes. These properties determine the worst-case performance of tree operations and guide algorithm design.
Tree balancing ensures that these properties result in O(log n) operation time. Without balancing, a BST that receives sorted input degenerates to a linked list with height n and all operations becoming O(n). This worst-case scenario occurs in practice when database IDs are monotonically increasing and are inserted into an unbalanced tree without rebalancing mechanisms.
Worst-Case and Average-Case Analysis
Understanding the performance characteristics of tree and graph algorithms requires analyzing both average-case and worst-case scenarios. For balanced BSTs, search, insertion, and deletion are O(log n) in both average and worst case. For unbalanced BSTs without self-balancing, the worst case is O(n) while the average case remains O(log n) for random insertions.
For graph traversal, BFS and DFS both achieve O(V+E) time in all cases, making them reliable for any graph topology. The space complexity differs significantly: BFS requires O(V) space for the queue in the worst case, while DFS requires O(h) space where h is the graph depth. For dense graphs, BFS memory usage can become prohibitive, while DFS remains efficient.
Common Graph Algorithms
Shortest path algorithms include Dijkstra’s for non-negative weights using a priority queue, Bellman-Ford for graphs with negative weights, and Floyd-Warshall for all-pairs shortest paths. Minimum spanning tree algorithms include Kruskal’s using union-find and Prim’s using a priority queue. Topological sort orders nodes in a DAG so dependencies come before dependents. Cycle detection identifies deadlocks and circular dependencies.
Tree and Graph Use Cases in Production
In production systems, trees and graphs power some of the most critical infrastructure. Database indexes including PostgreSQL’s B-tree indexes and MySQL’s B+tree indexes use balanced tree structures for O(log n) lookup on disk-based data. The Linux kernel uses Red-Black trees for the completely fair scheduler’s run queue. Git uses directed acyclic graphs to model commit history, enabling efficient branch management and merge operations.
Graph databases like Neo4j and Amazon Neptune are specialized for storing and querying highly connected data. Social networks use graph structures for friend recommendations and feed ranking. Recommendation systems use bipartite graphs connecting users to items for collaborative filtering. Google’s PageRank algorithm models the web as a directed graph of pages connected by links.
Tree Serialization and Deserialization
Serializing a tree to a string representation and reconstructing it is a common requirement for data storage, transmission, and caching. Preorder traversal combined with a sentinel marker for null nodes produces a unique serialization from which the tree can be perfectly reconstructed. This approach is used in distributed systems where tree structures need to be transmitted between services and in databases where indexes must be persisted to disk.
Level-order traversal with null markers also produces a unique serialization and can be more space-efficient for complete or nearly complete trees. The choice between preorder and level-order serialization depends on the tree’s shape and the expected distribution of null children. Balanced trees are efficiently serialized with either approach, while skewed trees benefit from preorder serialization. The serialization format must be carefully designed to ensure unambiguous reconstruction, particularly when node values can be any string that might be confused with the null marker.
Trie
A trie is a tree specialized for string storage and prefix matching, where each node represents a character and paths from root to marked nodes spell complete words. Tries excel at prefix-based operations including autocomplete, spell checking, IP routing, and DNA sequence matching. They provide O(m) operations where m is key length, independent of the total number of stored strings.
Frequently Asked Questions
What is the difference between a tree and a graph? A tree is a connected acyclic graph with exactly one path between any two nodes. A graph can have cycles, multiple paths, and no designated root.
Why do we need balanced trees? An unbalanced BST can degenerate into a linked list. Balanced trees maintain O(log n) operations through rotations.
What is the best tree traversal for sorted output? Inorder traversal produces elements in sorted order for BSTs. Preorder for serialization, postorder for deletion.
How do I choose between adjacency list and adjacency matrix? Use adjacency lists for sparse graphs. Use adjacency matrices for dense graphs where edge existence checks dominate.
What is a trie and when should I use it? A trie stores strings by characters for O(m) prefix-based operations. Use for autocomplete, spell checking, and IP routing.
Data Structures Overview — Hash Tables Guide — Graph Algorithms Guide