Introduction to trees

This lesson defines the tree as a hierarchical abstract data type, explains root, parent, child, and subtree, and contrasts trees with linear lists and graphs. Later pages cover terminology, types, traversals, and binary / BST implementations in C.

1) What is a tree?

A tree is a collection of nodes connected by edges with no cycles: there is exactly one path between any two nodes. One node is designated the root; every other node has exactly one parent and zero or more children. Nodes with no children are leaves.

Unlike a stack or queue (strictly linear), a tree models branching—file folders, HTML DOM, expression parse trees, and decision paths in games all map naturally to trees.

Schematic: a small rooted tree

Root at top; children hang below (typical drawing convention):

              A  ← root
            /   \
           B     C
          / \     \
         D   E     F  ← leaves (here: D, E, F)

2) Core ideas

• Subtree — Any node together with all its descendants forms a subtree rooted at that node.
• Depth — Number of edges from the root to a node (root has depth 0).
• Height — Maximum depth among leaves (a single-node tree has height 0 by common convention).
• Degree — Number of children of a node (a binary tree limits this to at most two).

Formal definitions and naming vary slightly by textbook; the next lesson, Tree terminology, aligns vocabulary for the rest of this tutorial.

3) Tree vs list vs graph

Trees sit between simple lists and general graphs:

A tree is a connected acyclic graph with a distinguished root—so every tree is a graph, but not every graph is a tree. See Tree versus graph for a fuller contrast.

4) Where trees show up in this tutorial

Later lessons cover binary trees and binary search trees (BST) in C—array and linked representations, insert/delete/search, and traversal orders (preorder, inorder, postorder, level order). Master this introduction first; then Tree types and Tree traversal methods build the roadmap for code.