Recursive tree functions: decide what returns

A recursive function on a binary tree is easy to write once you have decided, in one sentence, what a call on one node returns. That sentence is the function’s contract, for example “height(node) returns the number of nodes on the longest downward path from node, and 0 for an empty tree”. The code follows from it: the base case is the contract applied to an empty subtree, and the general case combines what the calls on the two children return, trusting them to keep the same contract. Two more decisions finish the design. What a call needs to know from above, such as its depth or the highest value so far, is passed down as a parameter; what its parent needs back, such as a height or a total, is returned up. When the answer itself is not what the parent needs, the call records it on the side. This lesson writes contracts first, builds test trees from level-order lists, and solves one problem in full, in four languages.

Write the contract before the code

The trees in this module are binary: each node holds a value and up to two children, left and right, and a missing child is None in Python, null in Java and JavaScript, and a null pointer in C++. A node’s subtree is the node and everything below it, and a leaf is a node with no children. NIST’s Dictionary of Algorithms and Data Structures puts the root at depth 0, makes each child one level deeper than its parent, and measures the height of a tree as the greatest distance of any node from the root, so a tree of one node has height 0. Other definitions count nodes instead, so that one node has height 1 and an empty tree 0. Both are in use, and the contract says which one a function means:

Now read the code off the contract. An empty subtree returns 0, because the contract says so. For a real node, the longest downward path is the node itself followed by the longer of the two paths below it, and if the calls on the children keep the contract, they return exactly those two lengths: 1 + max(height(node.left), height(node.right)). Trusting the calls on the children is not wishful thinking. It is induction on the size of the subtree: the contract holds for an empty subtree, and if it holds for every smaller subtree, the combining line makes it hold for this one. A loop invariant is argued the same way, as the lesson on dry runs and invariants shows, with “every smaller subtree” in place of “every pass so far”.

With the edge-counting contract only the base case changes: height(None) is −1, so that a leaf gets 1 + max(−1, −1) = 0. A base case that does not match the contract is the classic slip. If height(None) returned 1, every height would come out one too large, and nothing would crash to tell you.

Before writing any recursive tree function, answer three questions:

1. What does a call return for its subtree, and for an empty one? Write it as one sentence that names the function, as above.
2. What does it need to know from above? Anything that depends on the path from the root to the node, such as its depth, a running sum or the highest value so far, becomes a parameter.
3. Is the answer what the parent needs? If not, return what the parent needs, and record the answer separately.

Test trees from level-order lists

Recursive functions need trees to run on, and nested constructors typed by hand are slow to write and easy to get wrong. A compact way to write a test tree is a level-order list: the values row by row, from left to right, with None where a child is missing. A missing node has no children, so nothing more is listed for it, and the None values at the very end are left out. Here is the org chart this lesson uses, built from its list, printed as an outline and turned back into a list:

"""Test helpers for binary trees: build a tree from a level-order list, turn it back into one, and print it.

A level-order list reads the tree row by row, left to right. None marks a missing child; a missing node has no
children, so nothing more is listed for it, and None values at the very end are left out.
"""
import random
from collections import deque


class Node:
    def __init__(self, val, left=None, right=None):
        self.val = val
        self.left = left
        self.right = right


def from_level_order(values):
    """The tree that a level-order list describes, or None for an empty list."""
    if not values or values[0] is None:
        return None
    root = Node(values[0])
    waiting = deque([root])  # nodes whose children have not been read yet, in order
    i = 1
    while i < len(values):
        if not waiting:
            raise ValueError(f"{values[i:]} come after the last node: not a level-order list")
        parent = waiting.popleft()
        if values[i] is not None:
            parent.left = Node(values[i])
            waiting.append(parent.left)
        i += 1
        if i < len(values) and values[i] is not None:
            parent.right = Node(values[i])
            waiting.append(parent.right)
        i += 1
    return root


def to_level_order(root):
    """The level-order list of a tree: from_level_order(to_level_order(t)) rebuilds t."""
    values = []
    waiting = deque([root])
    while waiting:
        node = waiting.popleft()
        if node is None:
            values.append(None)
            continue
        values.append(node.val)
        waiting.append(node.left)
        waiting.append(node.right)
    while values and values[-1] is None:
        values.pop()
    return values


def show(root):
    """Prints the tree as an outline: every child under its parent, marked L (left) or R (right)."""
    if root is None:
        print("(empty tree)")
        return

    def children_of(node, indent):
        children = [(side, child) for side, child in (("L", node.left), ("R", node.right)) if child is not None]
        for k, (side, child) in enumerate(children):
            last = k == len(children) - 1
            print(f"{indent}{'└─' if last else '├─'} {side} {child.val}")
            children_of(child, indent + ("   " if last else "│  "))

    print(root.val)
    children_of(root, "")


def random_tree(rng, size, low=1, high=9):
    """A random tree of `size` nodes with values from low to high: each new node goes into a random empty place."""
    if size == 0:
        return None
    root = Node(rng.randint(low, high))
    places = [(root, "left"), (root, "right")]  # empty places where a new child can go
    for _ in range(size - 1):
        parent, side = places.pop(rng.randrange(len(places)))
        child = Node(rng.randint(low, high))
        setattr(parent, side, child)
        places += [(child, "left"), (child, "right")]
    return root


if __name__ == "__main__":
    chart = [6, 4, 8, 7, 3, 8, 5, 9, None, 5, None, None, 2]
    root = from_level_order(chart)
    show(root)
    print("back to a list:", to_level_order(root))
    print("same list:", to_level_order(root) == chart)
    rng = random.Random(7)
    trees = [random_tree(rng, rng.randint(0, 12)) for _ in range(500)]
    round_trips = all(to_level_order(from_level_order(to_level_order(t))) == to_level_order(t) for t in trees)
    print("500 random trees survive the round trip:", round_trips)

6
├─ L 4
│  ├─ L 7
│  │  └─ L 9
│  └─ R 3
│     └─ L 5
└─ R 8
   ├─ L 8
   │  └─ R 2
   └─ R 5
back to a list: [6, 4, 8, 7, 3, 8, 5, 9, None, 5, None, None, 2]
same list: True
500 random trees survive the round trip: True

from_level_order keeps a queue of the nodes whose children have not been read yet. Each node in turn takes the next two values of the list as its left and right child, and each real child joins the back of the queue, so the children are read in the same row-by-row order the list was written in. The queue is a collections.deque, which the Python documentation describes as having O(1) appends and pops at either end; list.pop(0) would move every remaining element instead. to_level_order walks the tree in the same order to make the list again, and the last line checks the round trip on 500 random trees, which random_tree builds by putting each new node in a random empty place. show marks every child L or R, so a left child cannot pass for a right one.

A list is only a test if everyone reads it the same way, and one other layout is common: the one Python’s heapq module uses for heaps, where the children of position i sit at positions 2 * i + 1 and 2 * i + 2. Here are both readings of two lists:

"""One list, two trees: the same values read as a level-order list and as array positions."""
from tree_tools import Node, from_level_order, show, to_level_order


def from_positions(values):
    """The other layout: the children of position i are at positions 2i + 1 and 2i + 2."""

    def build(i):
        if i >= len(values) or values[i] is None:
            return None
        return Node(values[i], build(2 * i + 1), build(2 * i + 2))

    return build(0)


for values in ([6, 4, 8, 7, 3, 8, 5, 9, None, 5, None, None, 2], [4, None, 7, 6, 9]):
    as_list, as_positions = from_level_order(values), from_positions(values)
    print(values)
    if to_level_order(as_list) == to_level_order(as_positions):
        print("both layouts give the same tree")
    else:
        print("as a level-order list:")
        show(as_list)
        print("as array positions:")
        show(as_positions)

[6, 4, 8, 7, 3, 8, 5, 9, None, 5, None, None, 2]
both layouts give the same tree
[4, None, 7, 6, 9]
as a level-order list:
4
└─ R 7
   ├─ L 6
   └─ R 9
as array positions:
4
└─ R 7

For the org chart the two agree, because every row above the last one is full. For [4, None, 7, 6, 9] they do not. As a level-order list, the missing left child of the 4 takes one place and no more, so 6 and 9 become the children of the 7. As array positions, places 3 and 4 belong to the children of that missing node, and 6 and 9 disappear without an error. When a test case comes from somewhere else, build it and print it before you trust what a failing test says.

Top-down or bottom-up: one problem, both ways

Here is a small problem to solve twice. In the org chart, every person who manages nobody sends one request up to the founder, and every manager on the way approves it once. How many approvals happen in all? A person at depth d has d managers above them, so the answer is the sum of the leaf depths: 11 for this chart.

Top-down, the depth goes down as a parameter. The contract: leaf_depth_sum(node, depth) returns the sum of the leaf depths in node’s subtree, where depth is node’s own depth. An empty subtree returns 0, a leaf returns its depth, and any other node returns the sum of its children’s answers, telling each child that it is one level deeper.

Bottom-up, nothing goes down, and each call returns a summary its parent can combine. The contract: leaves_and_depths(node) returns how many leaves the subtree has and the sum of their depths counted from node. A parent cannot just add its children’s sums, because each leaf is one level further from the parent than from the child, so it adds one more for every leaf below each child. That is why the summary carries the number of leaves as well.

"""The sum of leaf depths, written twice: top-down (the depth goes down) and bottom-up (a summary comes back up)."""
import random

from tree_tools import from_level_order, random_tree


def leaf_depth_sum(node, depth=0):
    """Top-down. Contract: the sum of the depths of the leaves in node's subtree, where `depth` is the depth of node
    itself. The root is at depth 0, so a leaf's depth is the number of nodes above it."""
    if node is None:
        return 0
    if node.left is None and node.right is None:
        return depth
    return leaf_depth_sum(node.left, depth + 1) + leaf_depth_sum(node.right, depth + 1)


def leaves_and_depths(node):
    """Bottom-up. Contract: (how many leaves node's subtree has, the sum of their depths counted from node)."""
    if node is None:
        return 0, 0
    if node.left is None and node.right is None:
        return 1, 0
    left_leaves, left_sum = leaves_and_depths(node.left)
    right_leaves, right_sum = leaves_and_depths(node.right)
    # Each leaf is one level further from node than from the child it sits under.
    return left_leaves + right_leaves, (left_sum + left_leaves) + (right_sum + right_leaves)


chart = from_level_order([6, 4, 8, 7, 3, 8, 5, 9, None, 5, None, None, 2])
leaves, total = leaves_and_depths(chart)
print("top-down: ", leaf_depth_sum(chart))
print("bottom-up:", total, f"(from {leaves} leaves)")
print("empty tree:", leaf_depth_sum(None), leaves_and_depths(None))
print("a lone root:", leaf_depth_sum(from_level_order([6])), leaves_and_depths(from_level_order([6])))

rng = random.Random(11)
trees = [random_tree(rng, rng.randint(0, 40)) for _ in range(1_000)]
print("agree on 1,000 random trees:", all(leaf_depth_sum(t) == leaves_and_depths(t)[1] for t in trees))

top-down:  11
bottom-up: 11 (from 4 leaves)
empty tree: 0 (0, 0)
a lone root: 0 (1, 0)
agree on 1,000 random trees: True

Both versions give 11 and agree on 1,000 random trees. The top-down one is shorter because depth is defined from the root downwards: a node cannot work out its depth from its own subtree, but its parent can simply tell it. The bottom-up version needed two numbers to say the same thing. That gives the rule of thumb:

Some problems need both directions at once. Checking that a binary search tree is valid, for example, passes down the range each value must fall in and returns up whether each subtree passed; a later lesson of this module builds it.

A problem solved in full: standouts in an org chart

The org chart from the list above has five standouts:

Brute force first

Carry the whole chain of managers down the tree, as a list that grows by one person on the way down and shrinks by one on the way back, and compare each person with every rating in it. It is correct by construction, and the stress test further down uses it as the reference. Its cost is the problem: a person at depth d is compared with d ratings, so the work is the sum of all the depths, O(n · h) for n people in a chart h levels deep. On a chain of 900 people that is 404,550 comparisons; on a complete chart of 1,023 people, 10 levels deep, it is 8,194. Both numbers are measured below.

What to notice

The test for each person needs one fact about the chain above them, its highest rating, and the brute force carries the whole chain to get it. Whenever the test at a node depends on the path from the root, ask which single summary of that path it needs, such as the highest value, the sum or the length, and pass only that down.

The top-down version, step by step

1. Write the contract: count(node, highest_above) returns the number of standouts in node’s subtree, given highest_above, the highest rating on the chain from the root down to node’s parent.
2. An empty subtree has no standouts: return 0.
3. The node is a standout when node.val >= highest_above.
4. Its children have one more person above them, so they are told max(highest_above, node.val).
5. Return 1 or 0 for the node, plus what the calls on its two children return.
6. Start the root with minus infinity: nobody is above the founder, and every rating is at least that.

The same function in four languages. The Python and JavaScript tabs run in your browser; the Java and C++ files are compiled and run in the session after them.

"""Standouts: count the people in an org chart rated at least as high as everyone above them."""
from tree_tools import from_level_order


def count_standouts(root):
    def count(node, highest_above):
        # Contract: the number of standouts in node's subtree, given highest_above, the highest rating on the
        # chain from the root down to node's parent.
        if node is None:
            return 0
        here = 1 if node.val >= highest_above else 0
        highest = max(highest_above, node.val)
        return here + count(node.left, highest) + count(node.right, highest)

    return count(root, float("-inf"))  # nobody is above the root, so it always counts


CASES = [
    ("the org chart", [6, 4, 8, 7, 3, 8, 5, 9, None, 5, None, None, 2]),
    ("an empty chart", []),
    ("the founder alone", [6]),
    ("everyone rated 7", [7, 7, 7, 7, None, 7]),
    ("ratings fall down a chain", [9, 8, None, 7, None, 6]),
    ("ratings rise down a chain", [1, None, 2, None, 3, None, 4]),
    ("beats the manager, not the founder", [5, 3, None, 4]),
]

if __name__ == "__main__":
    for label, values in CASES:
        print(f"{label:<36}{count_standouts(from_level_order(values))}")

the org chart                       5
an empty chart                      0
the founder alone                   1
everyone rated 7                    5
ratings fall down a chain           1
ratings rise down a chain           4
beats the manager, not the founder  1

// Standouts: count the people in an org chart rated at least as high as everyone above them.

class Node {
  constructor(val) {
    this.val = val;
    this.left = null;
    this.right = null;
  }
}

/** The tree that a level-order list describes (null marks a missing child), or null for an empty list. */
function fromLevelOrder(values) {
  if (values.length === 0 || values[0] === null) return null;
  const root = new Node(values[0]);
  const waiting = [root]; // nodes whose children have not been read yet
  let head = 0; // the next of them: a head index, because shift() moves every element
  let i = 1;
  while (i < values.length) {
    if (head === waiting.length) throw new Error(`${values.slice(i)} come after the last node: not a level-order list`);
    const parent = waiting[head++];
    if (values[i] !== null) waiting.push((parent.left = new Node(values[i])));
    i++;
    if (i < values.length && values[i] !== null) waiting.push((parent.right = new Node(values[i])));
    i++;
  }
  return root;
}

// Contract: the number of standouts in node's subtree, given highestAbove, the highest rating on the chain from the
// root down to node's parent.
function count(node, highestAbove) {
  if (node === null) return 0;
  const here = node.val >= highestAbove ? 1 : 0;
  const highest = Math.max(highestAbove, node.val);
  return here + count(node.left, highest) + count(node.right, highest);
}

function countStandouts(root) {
  return count(root, -Infinity); // nobody is above the root, so it always counts
}

const cases = [
  ["the org chart", [6, 4, 8, 7, 3, 8, 5, 9, null, 5, null, null, 2]],
  ["an empty chart", []],
  ["the founder alone", [6]],
  ["everyone rated 7", [7, 7, 7, 7, null, 7]],
  ["ratings fall down a chain", [9, 8, null, 7, null, 6]],
  ["ratings rise down a chain", [1, null, 2, null, 3, null, 4]],
  ["beats the manager, not the founder", [5, 3, null, 4]],
];
for (const [label, values] of cases) {
  console.log(label.padEnd(36) + countStandouts(fromLevelOrder(values)));
}

the org chart                       5
an empty chart                      0
the founder alone                   1
everyone rated 7                    5
ratings fall down a chain           1
ratings rise down a chain           4
beats the manager, not the founder  1

// Standouts: count the people in an org chart rated at least as high as everyone above them.
import java.util.ArrayDeque;
import java.util.Arrays;

public class Standouts {
    static final class Node {
        final int val;
        Node left, right;

        Node(int val) {
            this.val = val;
        }
    }

    /** The tree that a level-order list describes (null marks a missing child), or null for an empty list. */
    static Node fromLevelOrder(Integer[] values) {
        if (values.length == 0 || values[0] == null) return null;
        Node root = new Node(values[0]);
        ArrayDeque<Node> waiting = new ArrayDeque<>(); // nodes whose children have not been read yet
        waiting.add(root);
        int i = 1;
        while (i < values.length) {
            if (waiting.isEmpty()) {
                String rest = Arrays.toString(Arrays.copyOfRange(values, i, values.length));
                throw new IllegalArgumentException(rest + " come after the last node: not a level-order list");
            }
            Node parent = waiting.remove();
            if (values[i] != null) waiting.add(parent.left = new Node(values[i]));
            i++;
            if (i < values.length && values[i] != null) waiting.add(parent.right = new Node(values[i]));
            i++;
        }
        return root;
    }

    // Contract: the number of standouts in node's subtree, given highestAbove, the highest rating on the chain from
    // the root down to node's parent.
    static int count(Node node, int highestAbove) {
        if (node == null) return 0;
        int here = node.val >= highestAbove ? 1 : 0;
        int highest = Math.max(highestAbove, node.val);
        return here + count(node.left, highest) + count(node.right, highest);
    }

    static int countStandouts(Node root) {
        return count(root, Integer.MIN_VALUE); // every int is >= Integer.MIN_VALUE, so the root always counts
    }

    public static void main(String[] args) {
        Object[][] cases = {
            {"the org chart", new Integer[] {6, 4, 8, 7, 3, 8, 5, 9, null, 5, null, null, 2}},
            {"an empty chart", new Integer[] {}},
            {"the founder alone", new Integer[] {6}},
            {"everyone rated 7", new Integer[] {7, 7, 7, 7, null, 7}},
            {"ratings fall down a chain", new Integer[] {9, 8, null, 7, null, 6}},
            {"ratings rise down a chain", new Integer[] {1, null, 2, null, 3, null, 4}},
            {"beats the manager, not the founder", new Integer[] {5, 3, null, 4}},
        };
        for (Object[] c : cases) {
            System.out.printf("%-36s%d%n", c[0], countStandouts(fromLevelOrder((Integer[]) c[1])));
        }
    }
}

// Standouts: count the people in an org chart rated at least as high as everyone above them.
#include <algorithm>
#include <climits>
#include <iomanip>
#include <iostream>
#include <memory>
#include <optional>
#include <queue>
#include <stdexcept>
#include <string>
#include <utility>
#include <vector>

struct Node {
    int val;
    std::unique_ptr<Node> left, right;
    explicit Node(int v) : val(v) {}
};

// The tree that a level-order list describes (std::nullopt marks a missing child), or nullptr for an empty list.
std::unique_ptr<Node> from_level_order(const std::vector<std::optional<int>>& values) {
    if (values.empty() || !values[0]) return nullptr;
    auto root = std::make_unique<Node>(*values[0]);
    std::queue<Node*> waiting;  // nodes whose children have not been read yet
    waiting.push(root.get());
    std::size_t i = 1;
    while (i < values.size()) {
        if (waiting.empty()) throw std::invalid_argument("values come after the last node: not a level-order list");
        Node* parent = waiting.front();
        waiting.pop();
        if (values[i]) {
            parent->left = std::make_unique<Node>(*values[i]);
            waiting.push(parent->left.get());
        }
        ++i;
        if (i < values.size() && values[i]) {
            parent->right = std::make_unique<Node>(*values[i]);
            waiting.push(parent->right.get());
        }
        ++i;
    }
    return root;
}

// Contract: the number of standouts in node's subtree, given highest_above, the highest rating on the chain from
// the root down to node's parent.
int count(const Node* node, int highest_above) {
    if (node == nullptr) return 0;
    int here = node->val >= highest_above ? 1 : 0;
    int highest = std::max(highest_above, node->val);
    return here + count(node->left.get(), highest) + count(node->right.get(), highest);
}

int count_standouts(const Node* root) {
    return count(root, INT_MIN);  // every int is >= INT_MIN, so the root always counts
}

int main() {
    constexpr auto none = std::nullopt;
    const std::vector<std::pair<std::string, std::vector<std::optional<int>>>> cases = {
        {"the org chart", {6, 4, 8, 7, 3, 8, 5, 9, none, 5, none, none, 2}},
        {"an empty chart", {}},
        {"the founder alone", {6}},
        {"everyone rated 7", {7, 7, 7, 7, none, 7}},
        {"ratings fall down a chain", {9, 8, none, 7, none, 6}},
        {"ratings rise down a chain", {1, none, 2, none, 3, none, 4}},
        {"beats the manager, not the founder", {5, 3, none, 4}},
    };
    for (const auto& [label, values] : cases) {
        auto root = from_level_order(values);
        std::cout << std::left << std::setw(36) << label << count_standouts(root.get()) << '\n';
    }
}

The Java and C++ versions, compiled and run:

from session import run

run("""
java -version 2>&1 | head -n 1 | cut -d ' ' -f 1-3
java Standouts.java
clang++ --version | head -n 1
clang++ -std=c++23 -Wall -Wextra -fsanitize=address,undefined standouts.cpp -o standouts && ./standouts
""")

$ java -version 2>&1 | head -n 1 | cut -d ' ' -f 1-3
openjdk version "27"
$ java Standouts.java
the org chart                       5
an empty chart                      0
the founder alone                   1
everyone rated 7                    5
ratings fall down a chain           1
ratings rise down a chain           4
beats the manager, not the founder  1
$ clang++ --version | head -n 1
Apple clang version 21.0.0 (clang-2100.3.34.2)
$ clang++ -std=c++23 -Wall -Wextra -fsanitize=address,undefined standouts.cpp -o standouts && ./standouts
the org chart                       5
an empty chart                      0
the founder alone                   1
everyone rated 7                    5
ratings fall down a chain           1
ratings rise down a chain           4
beats the manager, not the founder  1

All four print the same seven answers. Java and C++ have no infinite int, so they start from the smallest int instead, Integer.MIN_VALUE and INT_MIN, which every rating is at least. Each language marks a missing child in its level-order list its own way: None, null, or std::nullopt in a list of std::optional<int>. The JavaScript builder keeps an index to the front of its queue instead of calling shift(), which, by the steps the ECMAScript specification gives, moves every remaining element one place. The C++ version is built with AddressSanitizer and UndefinedBehaviorSanitizer, which report invalid memory accesses and undefined behaviour while the program runs; this run reported none.

Why it is correct

The contract is the invariant, and induction on the size of the subtree proves it. An empty subtree has no standouts, so 0 is right. For a node, the contract says that highest_above is the highest rating on its chain, so node.val >= highest_above is exactly the definition of a standout. Each child’s chain is the node’s chain plus the node, whose highest rating is max(highest_above, node.val), so the calls on the children get the right argument and, being calls on smaller subtrees, return the right counts. The node’s own 1 or 0 plus their two counts is the count for its subtree.

A dry run

Every call on a node of the org chart, in the order the calls start. The down column is what the call passes to its children, and up is what it returns:

"""A dry run of count_standouts on the org chart: one row per call on a node, in the order the calls start."""
from tree_tools import from_level_order

rows = []  # [call, standout?, what it passes to its children, what it returns], filled in as the calls finish


def count(node, highest_above, depth=0):
    if node is None:
        return 0  # the calls on missing children are left out of the table: they all return 0
    here = 1 if node.val >= highest_above else 0
    highest = max(highest_above, node.val)
    row = ["  " * depth + f"count({node.val}, {highest_above})", here == 1, highest, None]
    rows.append(row)
    row[3] = here + count(node.left, highest, depth + 1) + count(node.right, highest, depth + 1)
    return row[3]


total = count(from_level_order([6, 4, 8, 7, 3, 8, 5, 9, None, 5, None, None, 2]), float("-inf"))
print(f"{'call':<18}{'standout':<10}{'down':<6}up")
for call, standout, passed, returned in rows:
    print(f"{call:<18}{'yes' if standout else 'no':<10}{passed:<6}{returned}")
print("standouts:", total)

call              standout  down  up
count(6, -inf)    yes       6     5
  count(4, 6)     no        6     2
    count(7, 6)   yes       7     2
      count(9, 7) yes       9     1
    count(3, 6)   no        6     0
      count(5, 6) no        6     0
  count(8, 6)     yes       8     2
    count(8, 8)   yes       8     1
      count(2, 8) no        8     0
    count(5, 8)   no        8     0
standouts: 5

Follow the left side of the chart. The call on the 4 passes 6 down, not 4, because the founder is still the highest rating above the 7 and the 3. That is why the 5 under the 3 is not a standout, although it is rated higher than its own manager. On the right, the second 8 passes 8 down, and the 2 below it falls short of that. Each row returns its own 1 or 0 plus what the rows directly below it return: the 4 returns 0 + 2 + 0 = 2.

The cost

The top-down version visits each person once and compares once. Both versions need O(h) extra space: the brute force for the chain it carries and for its calls, the top-down version for its calls alone, one frame for each level of the path being followed. That is about log₂ n levels for a balanced chart, and n for a chain.

Check it against the brute force

"""The brute force for standouts, a stress test of the fast version against it, and the work the brute force does."""
import random

from standouts import count_standouts
from tree_tools import Node, random_tree


def count_standouts_brute(root):
    """Carries the whole chain above each node down the tree and compares the node with every rating in it.
    Returns (standouts, ratings compared)."""
    compared = 0

    def count(node, chain):
        nonlocal compared
        if node is None:
            return 0
        here = 1
        for rating in chain:  # every rating above node
            compared += 1
            if rating > node.val:
                here = 0
        chain.append(node.val)
        found = here + count(node.left, chain) + count(node.right, chain)
        chain.pop()
        return found

    return count(root, []), compared


rng = random.Random(2024)
for trial in range(1_000):
    tree = random_tree(rng, rng.randint(0, 30), low=1, high=rng.choice([3, 9, 100]))
    if count_standouts(tree) != count_standouts_brute(tree)[0]:
        raise SystemExit(f"trial {trial}: the two versions disagree")
print("1,000 random trees: both versions agree")


def chain(n):
    """n nodes, each the only child of the one above it, with ratings rising: every node is a standout."""
    root = None
    for rating in range(n, 0, -1):
        root = Node(rating, left=root)
    return root


def complete(levels):
    """A complete tree with every level full, 2 ** levels - 1 nodes, everyone rated 1."""
    return None if levels == 0 else Node(1, complete(levels - 1), complete(levels - 1))


def size(node):
    return 0 if node is None else 1 + size(node.left) + size(node.right)


print(f"{'tree':<22}{'nodes':>6}{'standouts':>11}{'brute force compares':>22}")
for label, tree in (("a chain of 900", chain(900)), ("complete, 10 levels", complete(10))):
    found, compared = count_standouts_brute(tree)
    print(f"{label:<22}{size(tree):>6,}{found:>11,}{compared:>22,}")

1,000 random trees: both versions agree
tree                   nodes  standouts  brute force compares
a chain of 900           900        900               404,550
complete, 10 levels    1,023      1,023                 8,194

The random ratings come from three ranges, 1 to 3, 1 to 9 and 1 to 100, so that some charts are full of ties and others have almost none. The table measures the brute force’s work on the two shapes from the brute-force section. The top-down version compares once per person: 900 and 1,023 times.

Edge cases and common bugs

• An empty chart returns 0, and a chart of one person returns 1: the founder counts.
• Ties count. With > in place of >=, “everyone rated 7” gives 1 instead of 5, and the org chart 4 instead of 5.
• Starting from 0 instead of minus infinity works for this problem’s ratings, 1 to 100, and breaks as soon as a rating can be negative: a founder rated −5 would not count.
• A deep chart. The limit of 900 levels is in the problem for Python’s sake; the last section of this lesson measures why.

The most plausible bug passes the node’s own rating down instead of the highest rating so far, so each person is compared with their manager rather than with the whole chain:

"""A plausible bug: each rating is compared with the manager's rating only, not with the whole chain above it."""
from tree_tools import from_level_order


def count_beats_manager(root):
    def count(node, manager_rating):
        if node is None:
            return 0
        here = 1 if node.val >= manager_rating else 0
        return here + count(node.left, node.val) + count(node.right, node.val)  # passes its own rating, not the highest

    return count(root, float("-inf"))


print(count_beats_manager(from_level_order([6, 4, 8, 7, 3, 8, 5, 9, None, 5, None, None, 2])))

6

It finds one standout too many: the 5 under the 3 is rated at least as high as its manager, and lower than the founder.

Variants

• Strictly higher than everyone above: change >= to >. The founder still counts, because every rating is higher than minus infinity.
• At least the average of the chain above: pass two numbers down, the total of the ratings above and how many there are. This is the exercise below.
• List the standouts instead of counting them: append each standout to a list during the same pass. The list comes out in the order in which the calls start.

Follow-up questions

The chart arrives as (person, manager) pairs instead of a tree. What changes? Build a list of direct reports for each person in one pass over the pairs; the founder is the one person with no manager. The recursion stays the same, except that it loops over a person’s reports instead of visiting left and right, and a person may have any number of reports.

Can it run without recursion? Yes. Keep an explicit stack of (node, highest_above) pairs, start it with the root and minus infinity, and for each pair you pop, check the node and push its children with the updated highest rating. The order of the visits changes and the count does not, and the depth of the chart no longer matters, because the stack lives in ordinary memory.

Return one thing, record another

Sometimes the value a parent needs is not the answer. In the org chart, a team is a manager together with everyone below them, and the question is which team has the highest average rating. A manager’s average cannot be worked out from the averages of the teams below, because those teams have different sizes; it can be worked out from their totals and sizes. So each call returns what its parent needs, the (total, size) of its subtree, and records the answer, the best average so far, in a variable outside the calls:

"""The team with the highest average rating. A team is a manager and everyone below them, so a leaf leads no team.
Each call returns what its parent needs (the team's total and size) and records the answer on the side."""
from tree_tools import from_level_order


def best_team(root):
    best = None  # (average, the manager's rating) of the best team so far

    def total_and_size(node):
        # Contract: (sum of the ratings, number of people) of node's subtree. On the way, it records node's team.
        nonlocal best
        if node is None:
            return 0, 0
        left_total, left_size = total_and_size(node.left)
        right_total, right_size = total_and_size(node.right)
        total = node.val + left_total + right_total
        size = 1 + left_size + right_size
        if size > 1 and (best is None or total / size > best[0]):  # node manages someone, so it leads a team
            best = (total / size, node.val)
        return total, size

    total_and_size(root)
    return best


for values in ([6, 4, 8, 7, 3, 8, 5, 9, None, 5, None, None, 2], [5, 9, 1, 8], [6]):
    found = best_team(from_level_order(values))
    if found is None:
        print(values, "-> no team: nobody manages anyone")
    else:
        average, manager = found
        print(values, f"-> the team led by the person rated {manager}, average {average:.2f}")

[6, 4, 8, 7, 3, 8, 5, 9, None, 5, None, None, 2] -> the team led by the person rated 7, average 8.00
[5, 9, 1, 8] -> the team led by the person rated 9, average 8.50
[6] -> no team: nobody manages anyone

In the org chart the best team is the 7 and the 9, with an average of 8.00. A leaf leads no team, so a chart of one person has no team at all, and the function returns None rather than inventing an answer. The nonlocal statement lets the inner function rebind best; in Java a field or a one-element array plays the same part, and in C++ a reference parameter. The same shape, return what the parent needs and record what the question asks, computes the diameter of a tree in a later lesson of this module: each call returns a height and records the longest path that bends at its node.

How deep can recursion go?

Each call that has not returned yet keeps a frame on the call stack, so a recursive tree function needs about as many frames as the tree has levels, on top of the frames of the code that called it. CPython stops runaway recursion with RecursionError when the depth exceeds a limit, which sys.getrecursionlimit() reports. This program builds chains, trees in which every node has a single child, and runs the recursive height on them:

"""How deep a recursive tree function can go in Python before RecursionError, on a chain of nodes."""
import sys


class Node:
    def __init__(self, val, left=None):
        self.val = val
        self.left = left
        self.right = None


def chain(n):
    """n nodes, each the left child of the one above it: a tree n levels deep."""
    root = None
    for val in range(n):
        root = Node(val, left=root)
    return root


def height(node):
    """Contract: the number of nodes on the longest downward path from node; 0 for an empty tree."""
    if node is None:
        return 0
    return 1 + max(height(node.left), height(node.right))


def deepest_chain(limit):
    """The largest n for which height() finishes on a chain of n nodes (a binary search on n)."""
    lo, hi = 0, limit  # height() works for a chain of lo nodes and fails for hi
    while hi - lo > 1:
        mid = (lo + hi) // 2
        try:
            height(chain(mid))
            lo = mid
        except RecursionError:
            hi = mid
    return lo


print("recursion limit:", sys.getrecursionlimit())
for n in (900, 2_000, 100_000):
    try:
        print(f"chain of {n:,} nodes: height {height(chain(n)):,}")
    except RecursionError as error:
        print(f"chain of {n:,} nodes: RecursionError: {error}")
print("deepest chain that works:", deepest_chain(sys.getrecursionlimit()))

recursion limit: 1000
chain of 900 nodes: height 900
chain of 2,000 nodes: RecursionError: maximum recursion depth exceeded
chain of 100,000 nodes: RecursionError: maximum recursion depth exceeded
deepest chain that works: 997

The limit is 1,000 frames, and this height finishes on a chain of 997 nodes: the module, the function that searches for the deepest chain and the call on the empty child below the last node take the remaining frames. A complete tree of 100,000 nodes is only 17 levels deep, but a chain of 100,000 nodes needs 100,000 frames. A chain is the deepest tree for its number of nodes, so it is the first input to try when a problem allows large trees, and it is why the standouts problem says “at most 900 levels deep”. The Python documentation allows a higher limit with sys.setrecursionlimit() and warns that a limit set too high can crash Python. The dependable answer for deep trees is a loop with an explicit stack, which the next lesson of this module builds.

Exercise

# The lesson's org chart, [6, 4, 8, 7, 3, 8, 5, 9, None, 5, None, None, 2]
count_at_least_average(chart)  # 6

def count_at_least_average(root):
    """Count the nodes whose value is at least the average of the values above them."""
    # Replace this line with your code.
    return 0

import random
from collections import deque
from fractions import Fraction

from chain_average import count_at_least_average


class Node:
    def __init__(self, val, left=None, right=None):
        self.val = val
        self.left = left
        self.right = right


def tree(values):
    """The tree of a level-order list, as in the lesson: None marks a missing child."""
    if not values or values[0] is None:
        return None
    root = Node(values[0])
    waiting = deque([root])
    i = 1
    while i < len(values):
        parent = waiting.popleft()
        if values[i] is not None:
            parent.left = Node(values[i])
            waiting.append(parent.left)
        i += 1
        if i < len(values) and values[i] is not None:
            parent.right = Node(values[i])
            waiting.append(parent.right)
        i += 1
    return root


def chain(values):
    """A tree in which every node is the left child of the one before it."""
    root = None
    for v in reversed(values):
        root = Node(v, left=root)
    return root


def trusted(root):
    """The answer the tests trust: every node compared with the exact average of the whole path above it."""
    found = 0
    path = []
    stack = [(root, False)]
    while stack:
        node, leaving = stack.pop()
        if node is None:
            continue
        if leaving:
            path.pop()
            continue
        if not path or node.val >= Fraction(sum(path), len(path)):
            found += 1
        path.append(node.val)
        stack += [(node, True), (node.right, False), (node.left, False)]
    return found


def test_org_chart():
    """the lesson's org chart: 6 nodes count"""
    assert count_at_least_average(tree([6, 4, 8, 7, 3, 8, 5, 9, None, 5, None, None, 2])) == 6


def test_empty_tree():
    """an empty tree has nothing to count"""
    assert count_at_least_average(None) == 0


def test_root_alone():
    """the root has nothing above it, so it counts, whatever its value"""
    assert count_at_least_average(tree([-3])) == 1


def test_equal_to_the_average():
    """a value equal to the average counts: 3 is the average of 4 and 2"""
    assert count_at_least_average(tree([4, 2, None, 3])) == 2


def test_negative_values():
    """negative values: -1 is at least -3, -5 is not"""
    assert count_at_least_average(tree([-3, -5, -1])) == 2


def test_deep_chains():
    """chains 900 levels deep: rising values all count, falling values leave only the root"""
    assert count_at_least_average(chain(list(range(1, 901)))) == 900
    assert count_at_least_average(chain(list(range(900, 0, -1)))) == 1


def test_values_too_large_for_floats():
    """10**16 is below the average of 10**16 and 10**16 + 1, which a float rounds to 10**16"""
    assert count_at_least_average(tree([10**16, None, 10**16 + 1, 10**16])) == 2


def random_tree(rng, size):
    """A random tree of `size` nodes: each new node goes into a random empty place under the nodes so far."""
    if size == 0:
        return None
    root = Node(rng.randint(-5, 9))
    places = [(root, "left"), (root, "right")]
    for _ in range(size - 1):
        parent, side = places.pop(rng.randrange(len(places)))
        child = Node(rng.randint(-5, 9))
        setattr(parent, side, child)
        places += [(child, "left"), (child, "right")]
    return root


def level_order(root):
    """The level-order list of a tree, for messages."""
    values, waiting = [], deque([root])
    while waiting:
        node = waiting.popleft()
        values.append(None if node is None else node.val)
        if node is not None:
            waiting += [node.left, node.right]
    while values and values[-1] is None:
        values.pop()
    return values


def test_random_trees():
    """400 random trees, compared with exact averages"""
    rng = random.Random(8)
    for _ in range(400):
        root = random_tree(rng, rng.randint(0, 25))
        assert count_at_least_average(root) == trusted(root), f"the tree {level_order(root)}"

Interview questions

Fresher · What is the contract of a recursive tree function, and why should it say what an empty subtree returns?

The contract is one sentence saying what a call on any node returns for that node’s subtree, and what the call is given from above, such as “height(node) returns the number of nodes on the longest downward path from node”. It comes before the code because the code follows from it: the base case is the contract applied to an empty subtree, and the general case combines the children’s results, trusting the calls on them to keep the same contract, which is induction on the size of the subtree. The empty subtree matters because every missing child becomes a call on one, so a wrong value there reaches every leaf. If height(None) returned 1, every height would be one too large, with no error. A good contract also says whether depths and heights count nodes or edges, since both are in use.

Key takeaways

• Write the contract first: one sentence saying what a call returns for its subtree, including an empty one. The base case is that sentence applied to no nodes.
• Trust the calls on the children to keep the contract: that is induction on the size of the subtree, and it is what makes the combining line correct.
• Pass down what the path from the root defines, such as the depth or the highest value so far; return up what the subtree defines, such as a height, a size or a total.
• When the parent needs something other than the answer, return what it needs and record the answer separately.
• Build test trees from level-order lists, print them and check the round trip: the same list read as array positions can describe another tree.
• CPython’s default limit is 1,000 frames. A recursive height handled a chain of 997 nodes and failed on 2,000, so deep trees need a loop with an explicit stack.