Data Structures & Algorithms
Trees and Graphs
A tree is a hierarchical structure in which every node has exactly one path back to a single root, with no cycles - a parent can have several children, but a child has only one parent. A graph is more general: a set of nodes, called vertices, connected by edges that can go in any pattern, including cycles, and a tree is actually just a special case of a graph with that extra restriction applied. Both extend the node-with-references idea from linked lists, but allow a node to connect to more than one other node instead of just a single next.
Why it matters
- File systems, the HTML DOM, and org charts are naturally trees
- Anything with a strict one-parent hierarchy, folders inside folders, elements nested inside elements, is already shaped like a tree before any code is written.
- Route maps, social connections, and dependency graphs are naturally graphs
- A road network, a friend network, or which software packages depend on which others all involve connections that can form cycles and do not have a single root.
- Traversal algorithms taught on trees and graphs generalize to a huge share of real problems
- Once a problem is recognized as find the shortest path or visit everything reachable, the same breadth-first or depth-first approach applies regardless of the specific domain.
- Getting the traversal order wrong changes both correctness and performance
- Depth-first and breadth-first search explore in genuinely different orders, and for shortest path in an unweighted graph, only one of them actually gives the right answer.
Trees: hierarchy with one path down
A tree starts at a root node; every other node has exactly one parent and can have any number of children - a binary tree is the common special case where every node has at most two. A node with no children is a leaf. Traversing a tree usually means visiting every node using recursion, since a tree is naturally defined in terms of smaller trees: visit a node, then recursively visit each of its children.
class Node:
def __init__(self, value, left=None, right=None):
self.value = value
self.left = left
self.right = right
def print_all(node):
if node is None:
return
print(node.value)
print_all(node.left)
print_all(node.right)
tree = Node(1, Node(2), Node(3))
print_all(tree) # 1, 2, 3Graphs: any node can connect to any other
A graph is commonly represented in code as an adjacency list, a mapping from each node to the list of nodes it connects to directly. Edges can be directed, a one-way connection, or undirected, a two-way connection, and a graph can contain cycles a tree cannot. Because cycles are possible, traversing a graph requires tracking which nodes have already been visited, or a naive traversal can loop forever revisiting the same nodes.
from collections import deque
graph = {'a': ['b', 'c'], 'b': ['d'], 'c': ['d'], 'd': []}
def bfs(start):
visited = {start}
queue = deque([start])
order = []
while queue:
node = queue.popleft()
order.append(node)
for neighbor in graph[node]:
if neighbor not in visited:
visited.add(neighbor)
queue.append(neighbor)
return order
print(bfs('a')) # ['a', 'b', 'c', 'd']Mistakes people make here
- Not tracking visited nodes when traversing a graph
- Trees have no cycles, so a naive recursive traversal always terminates. A graph can have cycles, and a traversal that does not track which nodes it has already visited can loop forever revisiting the same ones.
- Assuming every tree is a binary tree
- A tree node can have any number of children in general; binary trees are a common and convenient special case, not the definition of a tree itself.
- Confusing a node's depth with its height
- Depth is a node's distance from the root; height is the distance from a node down to its deepest leaf. They are measured in opposite directions and are easy to swap by mistake when discussing a tree's shape.
- Choosing depth-first search when the problem actually wants a shortest path
- In an unweighted graph, breadth-first search visits nodes in order of distance from the start, which is exactly what guarantees the first time you reach a node is via a shortest path. Depth-first search explores as far as possible down one branch first and gives no such guarantee.
Strengths and trade-offs
Where it is strong
- Models real hierarchical and networked data directly, rather than forcing it into a flat list that loses the relationships.
- A large share of practical search and optimization problems reduce to a traversal or shortest-path question once the data is represented as a graph.
- Recursion maps naturally onto tree operations, since a tree is already defined in terms of smaller trees of the same shape.
The trade-offs
- A graph represented poorly, such as a dense matrix for what is actually a sparse set of connections, can waste a large amount of memory compared to an adjacency list.
- Traversal algorithms are easy to get subtly wrong; a missing visited check turns a correct-looking depth-first search into an infinite loop the moment the graph has a cycle.
- Neither structure is contiguous in memory the way an array is, so, like linked lists, both give up some cache-friendliness in exchange for their flexible shape.
Who needs this
Anyone working with hierarchical data such as UI trees, file systems, or org structures, networked data such as routes, dependencies, or social graphs, or preparing for algorithm-focused technical interviews, where traversal problems are a recurring category.
Questions about trees and graphs
- What's the difference between a tree and a graph, in one sentence?
- A tree is a graph with the extra restriction that there is exactly one path between the root and any other node, and no cycles; a graph in general allows any connection pattern, including cycles and multiple paths between two nodes.
- When should I use breadth-first search instead of depth-first search?
- Use breadth-first search when you need the shortest path in an unweighted graph, or need to process nodes in order of distance from a starting point. Use depth-first search when you need to explore as deep as possible along a branch before backtracking, such as detecting a cycle or exploring all possibilities in a search space.
- Does Python have a built-in tree or graph type?
- No dedicated built-in type for either. Trees and graphs are typically built from plain classes, as in the examples here, or represented as dictionaries and lists for a quick adjacency-list graph; specialized needs, like a heap-ordered tree, are covered by narrower standard library tools such as heapq.
- Why do I need to track visited nodes in a graph traversal but usually not in a tree traversal?
- Because a tree has no cycles by definition - recursing into children can never lead back to a node already visited, so termination is guaranteed. A graph can have cycles, so without tracking visited nodes, a traversal can revisit the same nodes indefinitely.