A hierarchy has one root and many branches
Every structure in Unit I was linear — one predecessor, one successor. A tree is the first structure where one thing can have several children at once.
After this lesson
You should be able to
- Name the parts of a tree: root, parent, child, leaf, sibling.
- Compute the depth of a node and the height of a tree.
- Distinguish a general tree from a binary tree.
Not everything is a line
A company's org chart is not a line. A CEO has several managers reporting in; each manager has several engineers. A family tree is not a line either — one couple can have several children, each of whom can have children of their own. A tree is the data structure that models this: one parent, any number of children.
Notice what stayed the same from Unit I: nodes and pointers. A tree node still holds data and pointers to other nodes — it just holds more than one pointer forward, instead of exactly one.
The vocabulary you will use all unit
The root is the one node with no parent — the top of the org chart. A leaf is a node with no children — an individual contributor with no one reporting to them. Two nodes with the same parent are siblings. The depth of a node is how many steps it is from the root; the height of the tree is the depth of its deepest leaf.
CEO depth 0
/ \
VP-Eng VP-Sales depth 1
/ \
Dev-1 Dev-2 depth 2
height of this tree = 2 (the deepest leaf, Dev-1 or Dev-2)General tree versus binary tree
In a general tree, a node can have any number of children, and they have no fixed order — a manager might have three, five, or ten reports. In a binary tree, every node has at most two children, and — this is the part beginners miss — those two positions are named and fixed: left and right. Swapping a node's left and right child produces a different tree, even if the values are the same.
Most of this unit is about binary trees specifically, because the ordering of left and right is what makes searching fast — that is Lesson 4's whole story. General trees still matter, which is why the next lesson shows how to represent one using the same left/right shape.
Try it yourself
For the org chart in this lesson, write a recursive C function that computes the height of a binary tree, then trace it by hand on the CEO example.
Need a hint?
A leaf has height 0. Otherwise, the height is 1 plus the taller of the two children's heights.
Check the worked solution
A NULL node is given height -1 so that a single-node tree correctly comes out to height 0 (1 + max(-1, -1)). This is the same recursive shape as CS105ES's factorial: a base case that stops the recursion, and a recursive case that combines the answers from smaller subproblems.
int height(struct Node *node)
{
if (node == NULL)
return -1;
int left = height(node->left);
int right = height(node->right);
return 1 + (left > right ? left : right);
}Quick check
What is the key difference between a general tree and a binary tree?
Why this lesson exists
Syllabus mapping
Introduction · Types of Trees
Maps to course outcome CO1.