Check if a given binary tree is completed. A complete binary tree is one in which every level of the binary tree is completely filled except possibly the last level. Furthermore, all nodes are as far left as possible.
Examples
5
/ \
3 8
/ \
1 4
is completed.
5
/ \
3 8
/ \ \
1 4 11
is not completed.
Corner Cases
What if the binary tree is null? Return true in this case.
Recursive: Check if index should not exist
/**
* public class TreeNode {
* public int key;
* public TreeNode left;
* public TreeNode right;
* public TreeNode(int key) {
* this.key = key;
* }
* }
*/
public class Solution {
public int countNode(TreeNode root){
if (root == null) return 0;
return (1 + countNode(root.left) + countNode(root.right));
}
public boolean completeHelper(TreeNode root, int index, int nodeCount){
if (root == null) return true;
if (index >= nodeCount) return false;
return completeHelper(root.left, 2 * index + 1, nodeCount) &&
completeHelper(root.right, 2 * index + 2, nodeCount);
}
public boolean isCompleted(TreeNode root) {
if (root == null) return true;
int nodeCount = countNode(root);
return completeHelper(root, 0, nodeCount);
}
}
// time complexity: countNode O(N) + CompleteHelper O(N) = O(2N) = O(N)
// space complexity: no new instance created. O(1)
BFS: toggle boolean on first node doesn't have both children
public class Solution {
public boolean isCompleted(TreeNode root) {
if (root == null) return true;
Queue<TreeNode> q = new LinkedList<>();
q.add(root);
boolean noMoreChildren = false;
while (noMoreChildren == false) {
// when we encounter a node with a null left or right child
// no further nodes are allowed with children
TreeNode current = q.poll();
if (current.left == null) {
noMoreChildren = true;
// check for illegal right-only branch
if (current.right != null) return false;
break;
}
q.add(current.left);
if (current.right == null) {
noMoreChildren = true;
break;
}
q.add(current.right);
}
while (!q.isEmpty()) {
TreeNode current = q.poll();
if (current.left != null || current.right != null) {
return false;
}
}
return true;
}
}
//time complexity: O(N) one pass
//space complexity: O(N/2) queue size max = O(N)