Lesson notes
These notes explain the problem and current implementation. They are a reading companion, not a verbatim transcript of the recording.
A rooted tree organizes nodes through parent-child relationships. Each reachable nonroot node has one parent, and following children does not create a cycle. The recording introduces this vocabulary, common tree forms, and the costs of working with them. A binary tree limits each node to at most two children; it does not automatically impose a search ordering.
Name the shape before choosing an operation
The root has no parent within the tree. A leaf has no children. A subtree consists of a node and all of its descendants. These terms let you describe a recursive function's input precisely: it often receives a subtree root and returns a fact about that complete subtree.
Depth and height need a counting convention. The course's maximum-depth exercise counts edges, so a root-only tree has depth zero and an empty tree uses minus one. Other sources count nodes. State the convention before comparing results; two different numbers can come from two consistent definitions.
Keep binary shape separate from search order
In a binary search tree, values in the left and right subtrees obey an ordering rule. In an ordinary binary tree, they do not. An in-order traversal produces sorted values only when the search-tree ordering holds. A balanced shape alone cannot create that ordering, and an ordered tree need not be balanced.
Search-tree operations follow a path whose cost depends on height. Balanced trees can have logarithmic height. An unbalanced tree built from an unfortunate insertion sequence can become a chain and require linear work. The correction above qualifies the recording's complexity claim with that balance assumption.
Decide what one recursive result means
A depth calculation asks each child for its height, then combines the two returned values. An ancestor calculation returns a different kind of information. Returning a value, returning a node identity, and mutating the tree are distinct contracts even when they use the same traversal structure.
Test an empty tree, a single node, a balanced shape, and a one-sided chain. Continue with Tree Traversal, then try Binary Tree Max Depth. Use the tree traversal tool to compare visit order without assuming that any particular traversal makes an arbitrary tree sorted.