“Now, each of these paths can have many nodes in them. For a balanced binary tree (like above), each leaf node will be at maximum depth.”
According to Wikipedia, the definition of a balanced binary tree is as follows, " A balanced binary tree is a binary tree structure in which the left and right subtrees of every node differ in height by no more than 1."
In the Space Complexity section of this problem, they provide an example of a balanced binary tree of 7 nodes. This also happens to be considered a complete binary tree as all nodes have a left and right child with the exception of the leaf nodes.
In a balanced binary tree, there are cases where all leaf nodes are not at maximum depth. Take for example, if we removed the children off of node 3 (nodes 6 and 7), node 3 would now be a leaf node.
It would still be a balanced binary tree because the height of subtree with root at 2 and 3 differ by no more than 1.
And node 3 would not be at “maximum depth” since it would be at level 2 (where the root is at level 1) and the other leaf nodes would be at level 3.
As I think about this more, I suspect that the authors meant to say complete binary trees, not balanced.