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 => true
2. Push root in queue
3. node = pop from queue
4. if node has 2 children

a. if haschlld
       i. push children in queue
  b. else
       i. return false
  c.  end if

5. 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 if

6. else
   a. haschild => false
7. end if

8. if queue is not empty -> go to step 3
9. return true

Subscribe - To get an automatic feed of all future posts subscribe here, or to receive them via email go here and enter your email address in the box. You can also like us on facebook and follow me on Twitter @akashag1001.