Trees
A structure that is recursive by construction: a tree is a value plus a list of trees. Every operation on it is the Unit 6 pattern with "subtree" in place of "element", and this is where recursion stops being optional and becomes the only sensible approach.
- Define a tree recursively and implement it.
- Compute size, height and membership recursively.
- Distinguish preorder, postorder and level order.
- Handle the empty tree deliberately.
Hierarchies are everywhere and lists cannot express them. A tree captures "this contains those" directly, and because the definition is recursive, every algorithm on it is too.
File systems, the DOM behind every web page, organisation charts, decision trees in machine learning, and the parse trees every compiler builds from source code.
The upside-down convention — root at the top, leaves at the bottom — is universal in computing and backwards from botany. It stuck because it reads naturally top to bottom on a page.
Definition and implementation
A tree is either empty, or a root value together with a list of subtrees, each itself a tree.
class Tree:
"""A tree with a root value and a list of subtrees.
Attributes:
_root: the value at this node, or None if the tree is empty
_subtrees: the subtrees of this node
Representation invariants:
- if self._root is None then self._subtrees == []
"""
_root: object
_subtrees: list
def __init__(self, root, subtrees: list) -> None:
"""Initialize a tree with the given root and subtrees.
An empty tree is Tree(None, []).
"""
self._root = root
self._subtrees = subtrees
def is_empty(self) -> bool:
"""Return whether this tree is empty."""
return self._root is NoneTree(None, [something]) would be a nonsensical
object every method would then have to cope with.Tree(value, []) — a root with
an empty subtree list, not an empty tree.Recursive operations
Every method follows the same three steps:
def method(self):
if self.is_empty():
return something for the empty tree
# combine self._root with method() on each subtreeCompare Unit 6. The only change is that "each element" has become "each subtree".
def __len__(self) -> int:
"""Return the number of values in this tree.
>>> t = Tree(1, [Tree(2, []), Tree(3, [])])
>>> len(t)
3
"""
if self.is_empty():
return 0
return 1 + sum(sub.__len__() for sub in self._subtrees)
def height(self) -> int:
"""Return the height of this tree.
An empty tree has height 0; a leaf has height 1.
>>> Tree(1, [Tree(2, [])]).height()
2
"""
if self.is_empty():
return 0
if self._subtrees == []:
return 1
return 1 + max(sub.height() for sub in self._subtrees)
def __contains__(self, item) -> bool:
"""Return whether item is a value in this tree.
>>> 2 in Tree(1, [Tree(2, [])])
True
"""
if self.is_empty():
return False
if self._root == item:
return True
return any(item in sub for sub in self._subtrees)height needs the leaf case separately, because
max cannot handle an empty subtree list — the same trap as
Unit 6.__contains__ stops early: any
short-circuits, so it will not search subtrees once the value is
found.These are different and both need handling. An empty tree has no root at all; a leaf has a root and no subtrees. Conflating them produces methods that crash on one or return nonsense on the other.
Traversal order
Visiting every value, in one of several orders:
def preorder(self) -> list:
"""Return the values of this tree, root before subtrees.
>>> Tree(1, [Tree(2, []), Tree(3, [])]).preorder()
[1, 2, 3]
"""
if self.is_empty():
return []
values = [self._root]
for sub in self._subtrees:
values.extend(sub.preorder())
return values
def postorder(self) -> list:
"""Return the values of this tree, subtrees before root.
>>> Tree(1, [Tree(2, []), Tree(3, [])]).postorder()
[2, 3, 1]
"""
if self.is_empty():
return []
values = []
for sub in self._subtrees:
values.extend(sub.postorder())
values.append(self._root)
return valuesself._root is
added. One line, entirely different output order.def level_order(self) -> list:
"""Return the values of this tree, one depth level at a time."""
if self.is_empty():
return []
values = []
pending = [self]
while pending != []:
current = pending.pop(0) # take from the front: FIFO
values.append(current._root)
pending.extend(current._subtrees)
return valuespop(0) for pop() turns
it into a stack and gives depth-first order instead. The same
one-character difference as before.• Treating the empty tree and a leaf as the same
case.
• Calling max on an empty subtree list in
height.
• Using append where extend is needed when
gathering subtree results.
• Off-by-one on height. Decide whether a leaf is $0$ or $1$ and document
it.
• Expecting level order to fall out of recursion. It needs a
queue.
Practice
Write out each answer before opening it. Original exercises written for this guide in the style of the course's weekly work.
Define a tree recursively.
Answer
What is the difference between an empty tree and a leaf?
Answer
Count the leaves of a tree.
Solution
def leaf_count(self) -> int:
"""Return the number of leaves in this tree."""
if self.is_empty():
return 0
if self._subtrees == []:
return 1
return sum(sub.leaf_count() for sub in self._subtrees)For a root $1$ with children $2$ and $3$, give preorder and postorder.
Answer
Computing the total size of a folder tree — which traversal?
Answer
Sum all values in a tree of integers.
Solution
def total(self) -> int:
"""Return the sum of the values in this tree."""
if self.is_empty():
return 0
return self._root + sum(sub.total() for sub in self._subtrees)Why does height need a separate leaf case?
Answer
max over an empty list of subtrees raises. A leaf must return
$1$ directly.What single change makes level_order depth-first?
Answer
pop(0) with pop(), turning the queue into a
stack. Same code, different traversal — the Unit 3 point
again.Expanded topic checklist
Course coverage. This unit is part of the complete CSC148H1 topic map. It should cover the following items before you move on:
- Definition. Recursive structure, and the empty tree versus a leaf.
- Recursive methods. Size, height, membership, and the three-case pattern.
- Traversals. Preorder, postorder, and what each is for.
- Level order. Why it needs a queue rather than recursion.
Trees are the main application of "recursion" in the calendar's topic list. Check Quercus for the assigned exercises; tree methods are standard assignment and exam material.
Recursive data, recursive code. Handle the empty case, do something with the root, recurse on each subtree, combine. Unit 8 constrains the shape to two subtrees and adds an ordering rule, which is what makes fast search possible.
Deep practice extensions
Use these after the main practice set. They push on definitions and edge cases rather than routine calculation.
Why is a tree naturally handled recursively?
Guide
When does postorder matter?
Guide
Why is it not recursive?
Guide
Why require that an empty tree has no subtrees?