The question this module answers: how do you compute something over data shaped like a hierarchy? A binary tree is a node with a value and up to two children, each the root of a smaller tree. That self-similarity is the whole trick: if you can answer the question for the left subtree and for the right subtree, you can usually answer it for the whole tree with one small step at the root.
ML context.
- Decision trees and ensembles: every prediction is a walk from the root to a leaf (lesson 10.14); gradient-boosted models are hundreds of such trees.
- Model structure: a PyTorch model is a tree of modules;
named_modules(), parameter counting and freezing layers are tree traversals. - Nested data: JSON configs, parse trees of code and text, hierarchical labels (animal → dog → terrier), file trees of a dataset.
- Index structures: binary search trees, B-trees in databases, k-d trees for nearest neighbours (lesson 9.10).
1. The problem: a value for every subtree
Task: for every node, compute the size of its subtree (the number of nodes in it, itself included). Think of counting parameters per module in a model.
The direct approach counts each subtree from scratch: