1
$\begingroup$

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.

$\endgroup$
  • $\begingroup$ Note that programming is offtopic here, so I removed references to a certain programming language. $\endgroup$ – Raphael Nov 1 '17 at 10:20
1
$\begingroup$

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$.
$\endgroup$
  • $\begingroup$ I cannot use a queue for this problem. $\endgroup$ – darylnak Oct 31 '17 at 21:20
  • $\begingroup$ What do you mean? $\endgroup$ – quicksort Oct 31 '17 at 21:22
  • $\begingroup$ Does your solution involve using a queue of some sort? $\endgroup$ – darylnak Oct 31 '17 at 21:36
  • $\begingroup$ What is the problem of using a queue? $\endgroup$ – quicksort Oct 31 '17 at 21:37
  • $\begingroup$ I cannot use any implementation of a queue in my code. $\endgroup$ – darylnak Oct 31 '17 at 21:48
0
$\begingroup$

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

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.