Case study: Mock interview complete binary tree

The transcript starts from here:

	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 Solution {
	public static void main(String[] args) {
	ArrayList<String> strings = new ArrayList<String>();
	strings.add("Hello, World!");
	strings.add("Welcome to CoderPad.");
	strings.add("This pad is running Java " + Runtime.version().feature());
	for (String string : strings) {
	System.out.println(string);
	}
	TreeNode root = new TreeNode(1);
	root.left = new TreeNode(2);
	root.right = new TreeNode(3);
	TreeNode rootleft = root.left;
	rootleft.left = new TreeNode(5);
	rootleft.right = null;
	//rootleft.right = new TreeNode(5);
	TreeNode rootright = root.right;
	rootright.left = new TreeNode(8);
	rootright.right = new TreeNode(7);
	System.out.println(isComplete(root));
	TreeNode root1 = new TreeNode(1);
	root1.left = new TreeNode(3);
	TreeNode rootleft1 = root1.left;
	rootleft1.left = new TreeNode(4);
	/*
	1
	/
	3
	/
	4
	1
	/\
	2 3
	/ /\
	5 7 8
	*/
	System.out.println(isComplete(root1));
	}
	// do level order traversal. If I see empty node, 2^ 0; 2 ^ 1
	public static boolean isComplete(TreeNode root) {
	ArrayDeque<TreeNode> q = new ArrayDeque<>();
	if (root != null) {
	q.add(root);
	}
	boolean noMoreChildren = false; // #1
	while (!q.isEmpty()) {
	boolean lastInlevelFound = false; // #2
	for (int i = 0; i < q.size(); i++) {
	TreeNode curr = q.removeFirst();
	if (curr.left != null) {
	if (lastInlevelFound || noMoreChildren) {
	return false;
	}
	q.add(curr.left);
	}
	else {
	lastInlevelFound = true; // true
	}
	if (curr.right != null) {
	if (lastInlevelFound || noMoreChildren) {
	return false;
	}
	q.add(curr.right);
	}
	else {
	lastInlevelFound = true; // true
	}
	}
	if (lastInlevelFound) {
	noMoreChildren = true;
	}
	}
	return true;
	}
	static class TreeNode {
	int val;
	TreeNode left;
	TreeNode right;
	TreeNode(int x) { val = x; }
	}
	}
	/*
	Given a binary tree, determine if it is a complete binary tree.
	Definition of a complete binary tree from Wikipedia:
	In a complete binary tree every level, except possibly the last, is completely filled, and all nodes in the last level are as far left as possible. It can have between 1 and 2h nodes inclusive at the last level h.
	Example 1:
	1
	/ \
	2 3
	/ \ /
	4 5 6
	Input: [1,2,3,4,5,6]
	Output: true
	Explanation: Every level before the last is full (ie. levels with node-values {1} and {2, 3}), and all nodes in the last level ({4, 5, 6}) are as far left as possible.
	Example 2:
	1
	/ \
	2 3
	/\ \
	4 5 7
	Input: [1,2,3,4,5,null,7]
	Output: false
	Explanation: The node with value 7 isn't as far left as possible.
	*/

view raw CompleteBinaryTree.java hosted with ❤ by GitHub

end here.