Trees tutorial

Trees. The move: trust each child to answer, then combine the answers at the node.

Ask the root lantern to count its family. It asks both children the same question, and it flows down. A missing child answers zero: the base case. Then the answers flow back up: each lantern adds its two, plus one.

Three lines: if the node is None, return the base. Call left and right. Combine.

The clue: the problem says binary tree, root or subtree, or asks for a depth or height.

Each node is visited once: O of n time. The stack holds one path: O of h space, the height. Now let's use it on Invert Binary Tree.