Trees

A total for every account

A pharmacy chain has 120,000 accounts arranged as a tree: head office, then zones, regions, cities and single stores. Every night, for each account, finance needs the total collected by everything under it.

The report does it the direct way. For each account, it scans all 120,000 accounts and asks of each one: are you under me? That check climbs the account's parent links, about six of them. Do the sum: 120,000 × 120,000 × 6 is about 86 billion steps. In Python that is well over two hours a night, and the chain is still opening stores.

Draw it small: head office, two zones, four stores, with a rupee amount under each store. Every store is under exactly one region, every region under one zone. The head office total is the sum of the zone totals, and nothing else.

Pause and predict To total the North zone, what should the zone ask each of its regions for?

Each subtree answers one question

A binary tree is either empty or a node with two smaller binary trees below it, its left and right subtrees. So most tree problems are solved by asking each subtree a question with a recursive call, and then combining the two answers at the node.

The skill is in choosing the question. In Maximum Depth, a node asks each child how deep its subtree is, and returns 1 plus the larger of the two answers.

Pause and predict Maximum Depth counts nodes, so a tree with a single node has depth 1. What must the call on an empty (null) child return for that to come out right?

This is enough to make every call correct, by induction on the size of the subtree. The call on null returns the right value, because the base case is chosen that way. A call on a node whose children return the right values also returns the right value, because the combining step needs nothing else. So every call, all the way up to the root, returns the right value.

The children must answer before the node can combine, so the node's own work comes after both recursive calls. That order is called post-order. Each node is visited once, so the time is O(n), and the call stack grows as deep as the tree, so the extra space is O(h), where h is the tree's height.

When the answer and the return value differ

Diameter asks for the length of the longest path between any two nodes, counted in edges. Every path has exactly one highest node, where it bends: the path comes up one side to that node and goes down the other. So for every node, measure the longest path that bends there, and keep the best of all of them.

Pause and predict Below a node, the left subtree has height 3 and the right subtree has height 3, so the longest path that bends at this node has 3 + 3 = 6 edges. What should the node's call return to its parent?

The parent cannot use the path that bends at this node. That path already uses the node's edges to both of its children. If it also continued up to the parent, the node would have three path edges, and a path can have at most two at any node. What the parent can extend is a path that goes down one side only, and the height describes the longest such path.

Keeping these two apart, the path that bends at the node and the path handed up to the parent, is where most mistakes in this unit happen. Maximum Path Sum has the same structure with sums of values in place of lengths, plus one change. If the best downward path on one side has a negative sum, the node uses 0 for that side instead, because a path is allowed to take nothing from that side.

Three directions

Most tree questions are answered from below. Two other kinds come up often enough to name: in some, a node needs information that only its ancestors have, and in others the question is about the levels of the tree.

For a binary search tree (BST), the downward kind matters most. The BST rule is about whole subtrees: every value in the right subtree of 5 must be larger than 5, however deep it is. So pass an interval (lo, hi) down, holding the smallest and largest values allowed at that point. Going left from a node, the node's value becomes the new hi; going right, it becomes the new lo. The interval then holds the rules of every ancestor at once.

Make the tree wide and shallow, one disk page per node, and it is how a database finds one row among millions in a few reads: System design: how a row is stored.

How to recognise it

These problems give you a tree. Read the question to decide which way information must flow: does each node compute its answer from below, does it need something from above, or is the question about levels?

Pause and predict You need the k-th smallest value in a BST. Which approach fits?

The ones that only look like it

• Nodes with several parents, or cycles: that is a graph. Recursing into children would count a shared node twice, or never stop on a cycle. Keep a set of visited nodes: BFS and DFS on graphs.
• Every combination or every arrangement: here the tree is the tree of choices you make, and you explore each branch and then undo it. That is backtracking.
• A choice at every node, such as whether to place a camera there or whether to rob that house: the same post-order walk, with each call returning a small tuple holding one answer per choice. That is tree DP in Unit 22, and it builds on this unit.

Where it bites

• Returning the bending path. l + r is compared with best, but only one side may be returned to the parent. On [1, 2, null, 3, 4], returning the bending path at 2 gives the root a path sum of 10, for a path that does not exist.
• Answering with the root's return value. The longest path may bend at a lower node and never pass through the root, so return best at the end.
• Checking a BST node only against its parent. A node can satisfy its parent and still break the rule of a higher ancestor. Pass the interval (lo, hi) down, or check that an in-order walk gives strictly increasing values.
• Rechecking the queue length inside the level loop. Children are added during the loop, so the length keeps changing. Save the size before the inner loop starts.
• Starting best at 0 in Maximum Path Sum when values can be negative. A path has at least one node, so if every value is negative the answer is negative, and 0 would be wrong.
• Serializing without markers for missing children. The tree with 1 as the left child of 3 and the tree with 1 as the right child of 3 both list as 3, 1, so the reader cannot tell them apart.

Pause and predict In Java, a tree has a single node holding 2147483647, the largest int. The check starts with the int bounds lo = Integer.MIN_VALUE and hi = Integer.MAX_VALUE. Is the tree reported as a valid BST?