Rooted Trees in Graph Theory

Mohammed Islam Hadjoudj

Expert Operations Research Engineer

1. What Is a Rooted Tree?

In graph theory, a tree is a connected graph with no cycles. A rooted tree is simply a tree in which one special vertex has been chosen as the root. That single choice gives every other node a clear sense of "up" (toward the root) and "down" (away from it), turning a plain tree into a hierarchy. The underlying mathematics, including the seven equivalent definitions of a tree and why it always has exactly n minus one edges, is covered in the guide to trees in graph theory.

A useful fact: a tree with n nodes always has exactly n - 1 edges, and there is precisely one path between any two nodes, no more, no less.

2. Key Terminology

• Root: the topmost node; the only node with no parent.
• Parent / Child: if an edge connects A (closer to the root) to B, then A is the parent and B is the child.
• Siblings: nodes that share the same parent.
• Leaf: a node with no children, an "end" of the tree.
• Internal node: any node that has at least one child.
• Ancestor / Descendant: nodes on the path up to the root / down from a node.
• Depth: the number of edges from the root to a node. The root has depth 0.
• Height: the longest distance from a node down to a leaf. The tree's height is the height of its root.
• Subtree: a node together with all of its descendants.

3. Rooted vs Unrooted Trees

An unrooted tree only describes which nodes are connected, there is no top or bottom. The moment you pick a root, the same set of edges gains direction: edges are now understood as pointing away from the root, so a rooted tree behaves like a special kind of directed graph. Choosing a different root produces a different hierarchy from the very same underlying tree.

4. How Rooted Trees Are Represented

There are three common ways to store a rooted tree in code:

• Parent array: store each node's parent in an array (parent[i]). Compact, and ideal for "walk up to the root" operations.
• Children lists: each node holds a list of its children, the most flexible representation for traversals.
• Left-child / right-sibling: a binary-style encoding that stores any n-ary tree using just two pointers per node.

5. Types of Rooted Trees

• Binary tree: every node has at most two children, a "left" and a "right".
• Binary search tree (BST): a binary tree kept in sorted order, so lookups take O(log n) time when balanced.
• N-ary tree: nodes may have any number of children, like a file-system folder.
• Balanced trees (AVL, red-black, B-trees) automatically keep their height small to guarantee fast operations.

6. Traversing a Rooted Tree

Visiting every node is called traversal, and there are two broad families:

• Depth-first (DFS): go as deep as possible before backtracking. For binary trees this comes in pre-order, in-order, and post-order variants.
• Breadth-first (BFS): visit all nodes at one depth before going deeper, also called level-order traversal.

If these sound familiar, that is because they are the same strategies used on general graphs. See our deep dive on BFS vs DFS.

Traversing a Rooted Tree in Python

A rooted tree stored as a children map needs no visited set. There are no cycles and every node has exactly one parent, so each of these traversals is a plain walk.

from collections import deque

tree = {
    'A': ['B', 'C'],   # A is the root
    'B': ['D', 'E'],
    'C': ['F'],
    'D': [], 'E': [],
    'F': ['G'],
    'G': [],
}

def preorder(tree, node, out=None):
    """Depth-first: record a node, then recurse into its children."""
    if out is None:
        out = []
    out.append(node)
    for child in tree[node]:
        preorder(tree, child, out)
    return out


def level_order(tree, root):
    """Breadth-first: finish one depth before starting the next."""
    queue = deque([root])
    out = []
    while queue:
        node = queue.popleft()
        out.append(node)
        queue.extend(tree[node])
    return out


def depths(tree, root):
    """Distance from the root down to every node."""
    depth = {root: 0}
    queue = deque([root])
    while queue:
        node = queue.popleft()
        for child in tree[node]:
            depth[child] = depth[node] + 1
            queue.append(child)
    return depth


print(preorder(tree, 'A'))       # ['A', 'B', 'D', 'E', 'C', 'F', 'G']
print(level_order(tree, 'A'))    # ['A', 'B', 'C', 'D', 'E', 'F', 'G']

d = depths(tree, 'A')
print(d)                         # {'A': 0, 'B': 1, 'C': 1, 'D': 2, 'E': 2, 'F': 2, 'G': 3}
print(max(d.values()))           # 3, the height of the tree
print([v for v in tree if not tree[v]])   # ['D', 'E', 'G'], the leaves

7. Real-World Applications

• File systems: folders and files form a rooted tree, with the root directory at the top.
• The HTML DOM: every web page is a rooted tree of elements, including the one you are reading.
• Databases: B-trees and B+-trees power the indexes that make queries fast.
• Compilers: source code is parsed into an abstract syntax tree (AST).
• Decision trees and heaps: machine-learning models and priority queues are both built on rooted trees.