COMP9123 — Data Structures & Algorithms
Week 4: Trees
Week 4 is where the course leaves linear structures behind and starts thinking in hierarchies. The lecture teaches the language of trees, shows how traversal order changes meaning, and then uses recursion because trees are naturally defined in terms of smaller trees.
The right question for this week is not just “what is a tree?” but “why does this problem want a branching model and which visit order matches the goal?”
Why Trees? When a List Stops Being the Right Shape
The lecture opens by asking a structural question. Some problems do not look like a sequence at all. Game strategies branch, file systems branch, document outlines branch, and organisation charts branch. Once one object can lead to several next objects, a list is the wrong mental model.
Hierarchy
A parent-child relation matters. Higher nodes organise lower nodes rather than merely appearing before them.
Branching choices
A node can have many children, so one position in the structure can open several possible next steps.
Subproblems inside the whole
Every subtree looks like a smaller version of the original object, which is why recursive algorithms fit so naturally.
| Lecture application | What the tree is modelling | Why a list is not enough |
|---|---|---|
| Organisation chart | Management and reporting structure | Each manager can supervise several branches at once. |
| OS file structure | Folders containing files and subfolders | Directories nest and branch instead of forming one chain. |
| Document structure | Book, chapter, section, subsection | One heading can own many smaller headings below it. |
Professor lens: before coding, ask whether the data is really “one next element at a time” or whether it has branching ownership, branching decisions, or branching decomposition. Week 4 is training that judgement.
Tree Vocabulary: Root, Leaf, Ancestor, Depth, Height
Tree algorithms become hard only when the language is vague. The lecture slows down here because these words are the grammar of every later tree proof and implementation.
| Term | Meaning | What students often mix up |
|---|---|---|
| Root | The unique node with no parent. | The root is not “the first inserted node” by definition; it is the structural top. |
| Internal vs external | Internal nodes have at least one child; external nodes are leaves. | A leaf can still store important data; leaf does not mean empty. |
| Ancestors / descendants | Parent, grandparent, and so on upward; children, grandchildren, and so on downward. | These relations are transitive, not just one edge long. |
| Depth | How far a node is from the root, counted upward by ancestors. | Depth looks upward, not downward. |
| Height | How far a node or tree can still reach downward to a deepest leaf. | Height looks downward, not upward. |
| Subtree | A node together with all of its descendants. | This is the natural recursive unit for both proofs and code. |
Ordered trees
The lecture explicitly notes that sibling order can matter. In an ordered tree, the children of a node have a prescribed left-to-right order, and traversals must respect it.
Lowest common ancestor
Two nodes can share many ancestors. The lowest common ancestor is the deepest node that still lies above both of them.
Tree ADT & Node Model: What Questions the Structure Must Answer
The Tree ADT in the slides is deliberately abstract. It tells you what a correct tree implementation should support before committing to a particular representation.
| ADT operation | What it asks | Why it matters |
|---|---|---|
size(), isEmpty() |
How large is the structure? | These are whole-tree questions about scale and emptiness. |
root(), parent(p) |
Where is a node in the hierarchy? | Upward navigation supports depth reasoning and ancestor logic. |
children(p), numChildren(p) |
What lies below this node? | Downward navigation drives traversals and recursive algorithms. |
isInternal(p), isExternal(p), isRoot(p) |
What structural role does this node play? | Many base cases are just tests on one of these predicates. |
What the Week 4 code bundle is teaching you to store
class Node(Generic[T]):
_value: T
_parent: Node[T]
_children: List[Node[T]]
_subtree_size: int
class Tree(Generic[T]):
_root: Node[T]
_size: int
def add_node(self, p, parent): ...
def remove_node(self, p): ...
def preorder(self, p, ls): ...
def postorder(self, p, ls): ...
The abstraction in the slides becomes concrete here: parent links support upward reasoning, child lists support branching traversal, and subtree metadata prepares you for tutorial-style aggregation problems.
The important design habit: separate the interface from the representation. “Tree” is the abstract behaviour. A linked node structure is one way of implementing it.
Preorder & Postorder: The Visit Timing Is the Whole Idea
Lists have one obvious forward traversal. Trees do not. The lecture's key message is that traversal order is not a small technicality. It changes what the visit sequence means.
Preorder
Visit the node before its children. This is the right fit when the parent sets context or when you want a top-down explanation of the structure.
Postorder
Visit all child subtrees before the node. This is the natural fit when the parent must combine information coming up from below.
Ordered-tree rule
If the tree is ordered, the traversal must respect the prescribed child order. Otherwise “the” traversal result is ambiguous.
| Lecture challenge example | Better traversal | Why |
|---|---|---|
| Company strategic decisions | Preorder | You want to see the big decision before its sub-decisions. |
| Chatbot interaction tree | Preorder | Conversation branches make sense only after the current prompt is seen. |
| File-system backup | Postorder | You often want to finish children before finishing the parent directory. |
| Cleaning a room / clearing a structure | Postorder | The container or parent is logically finished after its contents are handled. |
The size of a node's subtree depends on the sizes of all child subtrees below it.
So every child result must already be available before the parent can finish its own value.
That is exactly the dependency pattern of postorder: descendants first, parent second.
Binary Trees: Left and Right Become Part of the Meaning
A binary tree is the course's first important special case. The structure is still a tree, but now each internal node has at most two children, and those children are distinguished as left and right.
| Binary-tree feature | Meaning | Why it matters later |
|---|---|---|
| At most two children | Branching is limited to left and right positions. | This creates stronger structure than a general tree. |
| Left child / right child labels | The order is built into the node itself, not just its child list. | That makes inorder traversal possible. |
| Proper binary tree | Every internal node has exactly two children. | This version has especially clean counting properties. |
| Extra operations | leftChild(p), rightChild(p), sibling(p) |
The ADT becomes more specialised because the structure is more specialised. |
Expression trees
Internal nodes hold operators and leaves hold operands. Traversal order determines how the expression is reconstructed.
Decision trees
Internal nodes hold yes/no questions and leaves hold decisions. The tree models a branching reasoning process.
Preview of BSTs
Week 4 introduces the structure. Week 5 will add an ordering rule on top of it and turn it into a search tree.
Watch the wording: “binary” means at most two children, not automatically two children. The word proper is what adds the stronger exactly-two condition for internal nodes.
Inorder & Euler Tour: Binary-Specific Ways to Read the Tree
Inorder only makes sense once left and right have different roles. That is why it appears after binary trees are introduced, not before.
The core inorder idea
def in_order(v):
if v.left != null:
in_order(v.left)
visit(v)
if v.right != null:
in_order(v.right)
Left subtree, then node, then right subtree. That small change in visit timing is enough to make inorder behave very differently from preorder and postorder.
Printing arithmetic expressions
The slides extend inorder by printing an opening bracket before the left subtree and a closing bracket after the right subtree. That reconstructs the familiar infix expression with parentheses.
Euler tour viewpoint
Euler tour is the unifying picture: when you “walk around” a binary tree, each node is encountered three times. First visit gives preorder, second visit gives inorder, third visit gives postorder.
| Moment of visit in Euler tour | Traversal it matches | Interpretation |
|---|---|---|
| On the left | Preorder | Parent first, before descending into the left side. |
| From below | Inorder | Between finishing the left subtree and entering the right subtree. |
| On the right | Postorder | After both subtrees have been fully processed. |
Recursive Tree Code: Depth, Height, and Tutorial Thinking
The final lecture segment turns tree vocabulary into executable reasoning. Recursive code on trees works because a subtree is itself a tree, so the problem naturally breaks into smaller copies of the same shape.
Two recursive patterns straight from the slides
def depth(v):
if v.parent == null:
return 0
return depth(v.parent) + 1
def height(v):
if v.isExternal():
return 0
h = 0
for each child w of v:
h = max(h, height(w))
return h + 1
| Tutorial / code task | Best thinking pattern | Why it works |
|---|---|---|
| Compute subtree size for every node | Postorder aggregation | Each parent combines already-computed child sizes plus one for itself. |
Visit all nodes at level k left-to-right |
Carry current depth during traversal | The target level is a structural property, so traversal state should track level. |
| Compute balance factor at every node | Bottom-up height computation | Each balance factor depends on left and right subtree heights. |
| Find preorder successor of a node | Reason using traversal order, not by building the whole list | The tutorial is pushing you toward structural navigation rather than brute force. |
Best Week 4 habit: whenever the problem says “for every node,” stop and ask what each recursive call should return, what the base case is, and whether the parent should act before its children or after them.
Complexity rule from the last slide: if the method recurses on all children and does only constant extra work per node, the total cost is \(O(n)\). If it follows at most one child at each level, the cost is \(O(\text{height})\).
Quiz Hub & Revision Targets
Once you can describe the structure, the next step is to retrieve it without notes. Use the practice tools after you can already explain why a traversal order or recursive pattern is the right one.
You should be able to explain
Why trees model branching data better than lists, and why sibling order matters in ordered trees.
You should be able to distinguish
Depth vs height, preorder vs postorder, and general trees vs binary trees.
You should be able to design
A recursive algorithm that returns a value from each subtree and combines those values correctly at the parent.
Suggested sequence: reread the traversal sections, do the foundations page next for the induction and counting facts, then come back here for mixed practice once the ideas feel stable.