COMP9123 — Week 4

Foundations & proof moves

Week 4 foundations sharpen the mathematical side of trees: how induction supports recursive claims, which structural facts are worth memorising, and how to recognise when a tree algorithm is truly linear.

Induction refreshTree counting factsTutorial 4 problem-solving patterns

Induction for Tree Problems

Tutorial 4 opens by reminding you that induction is not optional background material. Recursive data structures and recursive algorithms almost force you to reason inductively.

Core idea

Prove the claim for the smallest relevant case, then show that if it holds for smaller instances, it also holds for the next one. For trees, the “smaller instance” is often a subtree or a smaller height.

Tutorial setting	Natural induction object	Why it fits
\(\sum_{i=0}^{n} 2^i = 2^{n+1} - 1\)	Integer \(n\)	The claim is indexed by input size, so ordinary induction is natural.
Fibonacci bound \(F(n) < 2^n\)	Integer \(n\)	The recurrence already relates the current case to smaller cases.
Traversal correctness on trees	Subtree or height	The parent result is built from claims about smaller child subtrees.

Useful translation: when your code says “assume the recursive call works on each child,” the proof version says “assume the claim holds for each smaller subtree.” Those are the same structural idea in different languages.

Quick check

Which pair of ingredients must every valid induction proof provide?

A recursion stack and a queue

A diagram and a contradiction

A base case and an induction step

A left subtree and a right subtree

Counting Facts & Binary-Tree Bounds

A few structural facts show up over and over in later design and analysis questions. These are worth knowing cold because they convert a vague tree question into a short derivation.

Fact	What it tells you	How it is used
A tree on \(n\) nodes has \(n-1\) edges	Trees are connected but cycle-free.	Useful whenever the question shifts between counting nodes and counting links.
A binary tree of height \(h\) has at most \(2^{h+1}-1\) nodes	Each level can at most double.	Connects height to maximum capacity.
In a proper binary tree, leaves = internal nodes + 1	Full branching creates a tight structural relation.	Appears in proof and counting questions about binary shapes.

Why the height bound matters: if the number of nodes can grow exponentially with height, then balanced trees can keep height logarithmic in the number of stored elements.

Quick check

How many edges does any tree with \(n\) nodes have?

\(n - 1\)

\(n\)

\(2n\)

\(\lfloor \log_2 n \rfloor\)

Linear-Time Tree Algorithms: What the Tutorial Is Really Training

Most of Tutorial 4 is not about memorising one solution. It is about recognising the recurring pattern behind tree algorithms: compute something for the children, then use those results to answer the question for the parent.

Core idea

If your recursive method touches each node a constant number of times and does only constant extra work at that node, the overall running time is linear in the number of nodes.

Tutorial problem	Right structural move	Complexity intuition
Subtree size for every node	Postorder combine of child sizes	Each node is processed once, so total work is \(O(n)\).
Visit nodes at level \(k\)	Traverse while tracking current depth and respecting left-to-right order	One pass over the tree is enough, so \(O(n)\) is achievable.
Balance factor for every node	Compute subtree heights bottom-up	Reusing child heights prevents repeated recomputation.
Diameter of a tree	Aggregate depth-like information upward	The strongest solutions avoid recomputing heights from scratch at each node.

1

Associate one small unit of work with each node when the traversal reaches it.

2

Observe that preorder, postorder, and similar recursive traversals visit each node a bounded number of times.

3

Summing constant work over \(n\) nodes gives \(O(n)\) total time.

Slide 55 takeaway. If the recursion follows all children, think \(O(n)\). If it follows at most one child per level, think \(O(\text{height})\).

Quick check

A recursive tree algorithm visits every node once and does only \(O(1)\) extra work at each node. What is its total running time?

\(O(\log n)\)

\(O(n)\)

\(O(n^2)\)

\(O(2^n)\)

Quick checks

The Week 4 foundations checks now sit directly under induction, counting, and linear-time reasoning above so you can test each proof move immediately after reading it.

Tutorial PDF review

Use the tutorial sheet after the study guide when you want to move from recognition to construction. The best self-test is whether you can design the algorithm before reading any solution.

Checklist for Tutorial 4. You should be able to explain how induction proves the warm-up claims, build preorder or postorder realisations of an array, compute subtree sizes in one bottom-up pass, visit a requested level in natural left-to-right order, reason about preorder successor without building the full traversal, and explain why balance factor or diameter questions reward bottom-up aggregation.