Completeness of binary tree - mock interview March 31, 2020 second algorithm. The interviewee wrote the code and tested the code. I verified that the analysis is correct, and the idea is excellent.

CompletenessBinaryTree.java

import java.io.*;
import java.util.*;

/*
 * To execute Java, please define "static void main" on a class
 * named Solution.
 *
 * If you need more classes, simply define them inline.
 */

 class Node {
     int val;
     Node left, right;
    
     public Node(int val) {
        this.val = val; 
     }
}  

class Solution {
  
  public boolean isCompleteBinaryTree(Node root) {
        if(root == null) return true;
        int count = getCount(root);  // 
        return isCompleteBinaryTree(root, 0, count);
  }   
  
  private boolean isCompleteBinaryTree(Node root, int idx, int count) {
     if(root == null) return true;
     if(idx >= count) return false;
     return isCompleteBinaryTree(root.left, 2*idx + 1, count)
         && isCompleteBinaryTree(root.right, 2*idx + 2, count);
  }
  
  private int getCount(Node root) {
    if(root == null) return 0;
    return 1 + getCount(root.left) + getCount(root.right);
  } 
    
  public static void main(String[] args) {
    Solution solver = new Solution();
    Node one = new Node(5);
    Node two = new Node(7);
    Node three = new Node(11);
    Node four = new Node(13);
    Node five = new Node(15);
    one.left = two;
    one.right = three;
    two.left = four;
    three.left = five;
    System.out.println(solver.isCompleteBinaryTree(one) == false);
  }
}


/* 
given a binary tree, define completeness - 
1. all levels are complete, no missing node
2. except last level, all nodes should stay left as possible.

   5 a  ------- 1
   / \
   7b 11d  --     2
   /
   13c   <- completeness    
   
   4
   
   0, 1, 2, 3   
   
   dfs(5, 0) - > dfs(7, 1) & dfs(11, 2)   
   
   dfs(7, 1) -> dfs(13, 3)  -> return true - preorder ->[0,1,3,2] ->      
   
    dfs(5, 0) - > dfs(7, 1) & dfs(11, 2)
   
   dfs(7, 1) -> dfs(13, 3)
   
   
   dfs(11, 2) -> dfs(15, 5)
   
    5   ------- 1
   / \
   7  11  --     2
   /  /
   13 15
   
   
        0
   
     1    3
   
   2
   
   
   dfs
   
   
  <- not complete, 7's right child, node value 15 is not leftmost as possible -> return false 
   
   class Node{
     public int val;
     public Node left, right; 
   }
   
   bool checkCompleteness(Node root)
   {
   }
 */