CareerCup

Using the following "definition" of complete tree:

A binary tree is complete if the leaf nodes are only at the last level, and that too on the left, without any gaps.

The idea is to do a breadth first search while maintaining a number n with each node. And when we enque its children, we give the left child number 2n and right child 2n+1.

If the BFS does not return numbers in order 1,2,3 ..., M. Then it is not a complete tree. Otherwise it is.

Pseudo Code:

bool checkCompleteTree (Tree root) {
  
    if (!root) return true;
    Queue <Pair <root, int>> q;
    q.Enque(new Pair(root, 1));  
    int prevNumber = 0;
   
    while(!q.isEmpty()) {
        Pair p = q.Deque();
        Tree node = p.first;
        int number = p.second;
        if (number != prev_number + 1) { 
            return false;
        }
        prev_number++;
        if (!node.Left && node.Right) {
            return false;
        }
        if (node.Left) {
            q.Enque(new Pair(node.Left, number*2));
        }
        if (node.Right) {
            q.Enque(new Pair(node.Right, number*2 + 1));
        }
    }
}

we can do it using BFS idea.
for every node popped we have to just check it it has both left and right children. If for any node this is not true i.e either it has no children or 1 child then we see for all the left over nodes in the queue if they have any children or not. if anyone of them has a child then its not complete binary tree else it is.

int isComBinTree(node *root,int ht)
{
    if(ht==1)
        return 1;
    if(root->right==NULL || root->left==NULL)
        return 0;
    return isComBinTree(root->right,ht-1) && isComBinTree(root->left,ht-1);
}

Where ht is the height of the tree and leaf nodes are assumed to be sub trees with height 1.

breath first using queue. record first encounter of null. after that if a node is poped, it is not complete binary tree. if the loop just finished without next node, it is complete binary tree.

One more way to answer the question is to compare height of left and right subtrees.
Do a post-order tree traversal and check: if in any node MinHeight(LeftSubtree) < MaxHeight(RightSubtree) retrun 'tree is not complete'

One more way to answer the question is to compare height of left and right subtrees.
Do a post-order tree traversal and check: if in any node MinHeight(LeftSubtree) < MaxHeight(RightSubtree) retrun 'tree is not complete'

The following code depends on definition that says in a complete binary tree all the nodes should have exactly 2 nodes (or) none.


boolean isCompleteBT(Node* root) {
If (*root != null) {
return ((*root->left == null && *root->right == null) || (*root->left != null && *root->right != null)) && isCompleteBT(*root->left) && isCompleteBT(*root->right);
}
return true;
}

the min and max depth should be the same

using the definition a tree of height h will have 2^h-1 nodes in it...count the number of nodes using any traversal using stack coz better then recursion and then find height of the tree then chk..