Case study: check completeness of binary tree

Here is the gist.

The interviewee wrote the excellent idea to figure out the completeness of binary tree. His idea is to calculate total nodes in the binary tree first, and then assign each node with a value based on the structure of tree, the root node has value 0, and left child is parent node's value * 2 + 1, right child is parent node's value * 2 + 2. And then if it is a complete binary tree, all nodes value should be in the range of [0, totalNodes - 1]. Apply preorder travesal, and check if node's value is smaller than total nodes.

	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)
	{
	}
	*/

view raw CompletenessBinaryTree.java hosted with ❤ by GitHub