Find height of deepest FULL level in binary tree

Question

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.

Answer 1

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$.

Answer 2

My solution unlike the answer you indicate in your post assumes a general tree.

The idea is to recursively traverse all children. When we reach a leaf node we know it cannot be a node with the maximum nodes possible and return -1. If the current node is an internal node then we have two possibilities: either there is a full node in one of its subtrees, or the node itself is full. So we recursively check each subtree. Upon return from a recursive call, we check if its return value is -1 or a positive one equal to the height of the full node. -1 means we have not found any.

When we finish scanning of all subtrees of the current node we must check if we found any full node in one of its subtrees. If found we return its height. If not we check whether the current node is full. If it is full we return the current height, else we return -1, i.e., we failed to find. The following pseudocode implements this idea.

 Search(node, height)
   if node is leaf
    return -1

   #search in subtrees
   max_height = -1
   loop on node's children |child|
     hgt = Search(child, height+1)
     if max_height < hgt
       max_height = hgt
    end-loop

    if max_height == -1 #no full node found in any of subtrees 
      if node's children count == MAX_NODES_POSSIBLE
        return height
      else
        return -1 
    else
      return max_height
 end-Search     

Initially we call Search(root, 0).