Question: WAP to find if a tree is complete or not?

Definition: A complete tree is a tree in which:
1) Every level, except possibly the last, is completely filled.
2) At last level, all nodes are as far left as possible.

i.e A complete tree is a tree which has a HEAP like structure.

Among above trees, left side tree is a complete tree but right side tree isn't.

Answer: One way to attack this problem is to get length of left and right subtree and compare if their value differs at most by 1. But in this approach, we can not confirm the 2nd condition.

Another approach, which I am able to think is if we traverse the tree using BFS and see if we get a node with no child or one child (left child if only 1 child) then all the nodes after that should not have any child. This will confirm both the conditions and if this is true the tree is a complete tree.

Above is true for binary as well as for N-ary tree.

Algorithm:
This is for binary tree but can be extended for N-ary tree very easily:

` 1. bool haschild => true2. Push root in queue3. node = pop from queue4. if node has 2 childrena. if haschlld       i. push children in queue  b. else       i. return false  c.  end if5. else if node has one child   a. if right child OR haschild is false       i. return false  b. else       i. push child in queue       ii. haschild => false  c. end if6. else   a. haschild => false7. end if8. if queue is not empty -> go to step 39. return true`