Trees

One root, no cycles, and children under each node. Depth here is the number of nodes on the longest path down.

A tree is a set of nodes with one root and no cycles. Each node has zero or more children. A node with no children is a leaf. A binary tree gives each node at most two children, usually called left and right.

Depth of a node is how far it sits below the root. In this course, the depth of the tree means the number of nodes on the longest path from the root down. An empty tree has depth 0. A single node has depth 1. People also say height for a closely related count. Use the definition in front of you when you write the return value, or you will be off by one against the tests.

The recursive rule is the algorithm. An empty tree has depth 0. Otherwise the depth is 1 plus the larger of the children's depths. That walk is depth-first: one branch finishes before the other. Visiting every node on one level before the next level is a different walk, and it wants a queue.