09/04/2017

[Java] Find if binary tree is complete

A binary tree is complete if for each level, there are no holes between two children. For example:

complete =
        A
      B  C
there are no holes between B and C

complete =
        A
       B
there are no holes after B

non complete =
       A
        C
there is a hole before C

You can the code on my Gist (isTreeComplete) along with some test cases:

 /*  
   is tree complete  
   A tree is complete if for each level, there are no holes between children:  
   complete =  
     A  
    B C  
    no holes between B and C  
   
    complete =  
     A  
     B  
    no holes after B  
   
    non complete =  
     A  
     C  
    hole before C  
   */  
   public static boolean isTreeComplete(BST root){  
     //null root is always complete  
     if(root == null) return true;  
   
     /*  
     otherwise, we must NOT have null nodes between two nodes at each level  
     so do a BFS BUT CAUTION: track also NULL children, then check we do not have a non null node after we encountered a null one  
     */  
     Queue<BST> levels = new LinkedList<>();  
     boolean has_null = false;  
   
     levels.add(root);  
   
     while(!levels.isEmpty()){  
       BST t = levels.remove();  
   
       //if current node is not null  
       if(t != null) {  
         //if we had a null, fail  
         if(has_null) return false;  
         //otherwise add its children  
         levels.add(t.left);  
         levels.add(t.right);  
       }  
   
       //track if the node we just saw was null. CAUTION: do not overwrite it!  
       has_null = has_null || t == null;  
     }  
   
     //if we navigated the whole tree without problem, it is complete  
     return true;  
   }  

No comments:

Post a Comment

With great power comes great responsibility.

Da grandi poteri derivano grandi responsabilità.