Rooted Trees in Graph Theory

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.

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.

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.