Trees & Graphs

Trees and graphs are data structures used to represent hierarchical or networked relationships between elements, and traversing them correctly is a common focus in technical interviews.

Trees. A tree is a hierarchical structure with a single root node, where each node can have child nodes, and there are no cycles (no path leads back to an ancestor). Binary trees, where each node has at most two children, are a particularly common special case, with binary search trees adding an ordering property that makes searching efficient.

Tree traversal. Common ways of visiting every node in a tree include depth-first traversal (going as deep as possible along each branch before backtracking, with common variants like pre-order, in-order, and post-order depending on when a node is processed relative to its children) and breadth-first traversal (visiting all nodes at the current depth level before moving to the next level).

Graphs. A graph is a more general structure than a tree, consisting of nodes (vertices) connected by edges, without the restriction against cycles that trees have. Graphs can be directed (edges have a specific direction) or undirected, and weighted (edges have an associated cost or value) or unweighted.

Graph traversal. Similar to trees, graphs are commonly traversed using depth-first search or breadth-first search, adapted to handle the possibility of cycles (typically by tracking which nodes have already been visited, to avoid infinite loops).

Common applications. Trees are commonly used to represent hierarchical data (like a file system or an organizational structure), while graphs are commonly used to represent networks (like social connections, road networks, or dependency relationships between tasks).

Binary search trees and the balance problem. A binary search tree maintains the invariant that everything in a node's left subtree is smaller than the node and everything in its right subtree is larger, which is what allows search, insertion, and deletion to follow a single path from the root rather than examining every node. That path is short only when the tree is balanced: inserting already-sorted values produces a tree that is effectively a linked list, and operations degrade from O(log n) to O(n). Self-balancing variants exist precisely to guarantee the tree stays shallow, and this degradation is the reason most standard library ordered containers use one.

In-order traversal as a sorting property. The three depth-first orders are not interchangeable, and choosing the right one is often the whole solution. In-order traversal of a binary search tree visits values in sorted order, which makes it the natural way to validate a BST, find the kth smallest element, or emit contents in order. Pre-order suits copying or serializing a structure, since a node is handled before its children exist. Post-order suits deletion and any computation where a node's result depends on results from its children, such as computing height or aggregating subtree totals.

Recursion, explicit stacks, and depth. Depth-first traversal is naturally recursive, and the recursive form is almost always clearer. The cost is stack space proportional to the depth of the structure, so a deep or degenerate tree can exhaust the call stack on large inputs. Converting to an iterative traversal with an explicit stack removes that limit at the cost of readability. Breadth-first traversal is the mirror image: it uses an explicit queue rather than recursion, and its memory cost is proportional to the widest level rather than the depth.

Representing a graph. The two standard representations are an adjacency list, which stores each vertex's neighbors, and an adjacency matrix, which stores a value for every possible pair. Adjacency lists use space proportional to the number of vertices plus edges and make iterating a vertex's neighbors efficient, which suits the sparse graphs that dominate real applications. Adjacency matrices use space proportional to the square of the vertex count but answer "is there an edge between these two?" in constant time, which suits dense graphs. Choosing the wrong representation can turn a linear algorithm quadratic, so it is a decision worth making deliberately.

BFS, DFS, and shortest paths. On an unweighted graph, breadth-first search finds the shortest path in terms of edge count, because it reaches every vertex at the earliest possible level — a property depth-first search does not have, since it can arrive at a vertex by a long path first. Depth-first search is the natural fit for questions about reachability, connected components, cycle detection, and topological ordering of a directed acyclic graph. When edges carry weights, neither suffices unmodified, and weighted shortest-path algorithms such as Dijkstra's are the appropriate tool. Both traversals run in O(V + E) time on an adjacency list.

Tracking visited nodes. The single most common graph bug is omitting or mishandling the visited set, which on a cyclic graph produces infinite recursion rather than a wrong answer. Marking a vertex as visited when it is first enqueued or first entered — rather than when it is finished — also prevents the same vertex being queued repeatedly, which otherwise degrades performance badly on dense graphs. Trees do not need this bookkeeping precisely because they are acyclic, which is why tree code adapted to graphs without adding it fails immediately.

How to approach these problems. Establish the structure first: is it a tree or a general graph, directed or undirected, weighted or unweighted, connected or possibly not. Those four answers determine the algorithm almost entirely. Then pick the traversal that matches the question — BFS for shortest hops or level-by-level work, DFS for exhaustive exploration and structural properties — and confirm the base cases: an empty structure, a single node, and a disconnected component that a traversal from one starting vertex would never reach.

Understanding trees and graphs — their structure, common traversal techniques, and the distinction between them — provides the foundation for a large category of algorithmic problems involving hierarchical or networked data.