Find height of deepest FULL level in binary tree Suppose I have a binary tree that is guaranteed to have at least one level that holds the maximum amount of nodes possible. I want to find the height of the deepest level that is full/holds the maximum amount of nodes possible. I have a function highestFull() that calls it's recursive version highestFull(Node* t) which is initially given the root. I cannot use any of the standard library functions.

How do I approach this problem? I am looking for the most intuitive solution, not the most clever. I found an answer here, but I cannot understand why it works. I really want to understand the thought process behind the solution.
How would you determine the answer if you were looking at a graphical representation of the tree? You would scan all the levels from the root downwards until you found one that isn't full.

Formally, that is a breadth-first search of the tree that stops whenever a node with less than two children is found. Since you are working on a tree rather than a generic graph, you may rewrite it as follows:


Let $Q$ be a new queue of nodes, initially containing only the root.
While $v$, the first element of $Q$, has two children $v_l$ and $v_r$, remove $v$ and enqueue both $v_l$ and $v_r$.