Where it runs
1. The problem
The calls of a recursive function branch: one call makes two, and each of those makes two more. Now the data itself will branch. Each item can have several children instead of one "next" item, as in a linked list.
One example of such a structure is the folders on your computer. The top folder holds files and other folders, those hold more folders, and so on to the bottom. The first two questions people usually ask are: how many items are in here in total, and how deeply are they nested? A backup tool needs the number of files. A linter (a program that checks a project for errors and bad habits) needs the depth, so it can warn you when folders are nested ten levels deep.
This branching structure is called a tree. Each item of a tree is a node: it holds a value and links to its children. The single node at the top, the one with no parent, is the root. A node with no children is a leaf. In this lesson the tree is binary: each node has at most two children, left and right. A node looks like { val, left, right }, and a missing child is null.
Walking a tree in a set order comes in the next lesson. First come the two simplest measurements: the size (how many nodes) and the height (how many levels). Both are computed the same way.
This step is part of the paid track
The first 33 steps are open to everyone: lesson, exercise and tests. This one opens with full access. Start with a free account and the free steps.
Create a free accountSee what is includedOn LeetCode
Binary tree problems that measure the whole tree, such as its depth or its number of nodes. Answer for an empty tree, then combine the answers of the left and right subtrees.
The lesson's height under another name.
The lesson's countNodes passes as written, and the tree being complete allows a faster trick you can try after.
Like height with min instead of max, but a node with one child must not count its empty side.
The same height with a loop over a list of children instead of left and right.