Quiz
Warm-up from lesson 4-1: a linked list node holds a value plus ONE pointer to the next node. What do you get if a node may instead point to SEVERAL other nodes, with no cycles back?
Data with a hierarchy
Lots of data is naturally nested: folders inside folders, HTML elements inside elements, company org charts, replies under comments. The structure for nesting is the tree.
The vocabulary (used constantly, learn it now):
- root: the single top node
- child / parent: a node directly below / above another
- leaf: a node with no children
- subtree: any node plus everything below it, itself a complete tree
- depth of a node: how many steps it sits below the root
- height of a tree: the longest root-to-leaf path
That subtree point is why recursion (from Advanced Python) fits trees so perfectly: every child of a node is the root of a smaller tree, so a function that handles a node can just call itself on each child.
Code exercise · python
Run this. A tree node is a value plus a LIST of children (compare: a linked list node held one next pointer). Both functions use the subtree idea: handle this node, recurse on each child.
Code exercise · python
Your turn: implement `count_leaves(node)` on the same file-system tree. Use the subtree idea: a node with no children IS a leaf (count 1); otherwise its leaf count is the sum of its children's leaf counts. Compare with `count_nodes` above — only the base case and the combining step change.
Quiz
In the file system tree above, which statement is FALSE?