Card 01/ 08
Tree Patterns: Passing Values Down or Returning Them Up
A recursive call can carry what it learnt on the way down, return what it found below, or both, and the question decides which.
A recursive visit of a binary tree can pass a value down to each child as an argument, return a value up to the parent, or do both, and which one a question needs follows from where its answer comes from. When the answer at a node depends on the path that led to it, such as its depth or the sum of the values above it, the value travels down. When it depends on what lies beneath the node, such as its height or the size of its subtree, the value travels up. Binary trees, depth and height are the Binary Trees topic in Data Structures; here, as there, both are counted in edges, so a leaf has height 0 and an empty tree height −1.
The pattern keeps one invariant: each call answers for its own subtree and trusts the calls on its children to have answered for theirs. The tree 5, with children 9 and 7, shows both directions at once. Each call receives its depth from its parent and returns its height.
What height does the call on the root return?
- The deepest leaf, 8, is three edges below the root, along 5, 9, 2, 8. The root learns that from its children alone: 9 returns 2 and 7 returns 1, and the root adds one to the larger.
Each node's note gives the depth its call received and the height it returned, from the run. The depths are known on the way down, before a call looks at its children; the heights are known only on the way back up, after both children have answered.
5, receives depth 0, returns height 3
9, receives depth 1, returns height 2
4, receives depth 2, returns height 0
2, receives depth 2, returns height 1
null, empty left child, returns −1
8, receives depth 3, returns height 0
7, receives depth 1, returns height 1
null, empty left child, returns −1
6, receives depth 2, returns height 0
A third value can be recorded on the way rather than passed: here, the longest path between two nodes, which the walkthrough builds from the two heights each call hears. Every node is visited once whatever travels, so each version is O(n) time for n nodes, with O(h) space for the recursion on a tree of height h.
An organisation's chain of command works the same way: instructions travel down from the top and gather context on the way, and each team's summary travels up to its manager, who combines the two summaries below. The likeness breaks at what each person can see. A manager can ask anyone in the company, while a call sees only its own node, what its parent handed it and what its two children return.
← → move through sections and cards