Trees

Understanding Trees

A tree is a special kind of graph: connected, with no cycles, and exactly one fewer edge than vertices. This simple structure turns out to be one of the most useful in computer science, because it naturally represents hierarchy — file systems, organization charts, decision processes, and search structures are all trees. This module lets you check whether a graph qualifies as a tree and walk through the three classic ways to visit every node.

Key Definitions & Formulas

• Root: the top node of a tree, with no parent.
• Leaf: a node with no children.
• Binary tree: every node has at most two children.
• Preorder traversal: visit node, then left subtree, then right subtree.
• Inorder traversal: visit left subtree, then node, then right subtree.
• Postorder traversal: visit left subtree, then right subtree, then node.

Worked Example

For the tree with root 1, left child 2, and right child 3 (2 also has a right child 5): preorder visits 1 → 2 → 5 → 3 (node first, then dive left before right), while inorder visits 2 → 5 → 1 → 3 (left subtree fully processed before the node itself is recorded).

Where This Is Used

• File system directory structures.
• Binary search trees for fast lookup, insertion, and deletion.
• Parsing expressions in compilers (expression/syntax trees).
• Decision trees in machine learning and rule-based systems.