Is this binary tree complete or not

Question

Given a binary tree, write a function to check if a given binary tree is a complete binary tree or not.

A complete binary tree is a binary tree in which each level, with the possible exception of the last one, is completely populated, and all nodes are as far as possible. source: wikipedia

My approach does BFS using a queue and counts the number of nodes. Run the loop until the queue is zero, but break once when you find one of the conditions below:

• left node is not for node
• The left node is present, but the right node is not.

Now we can compare the score we get from the above approach with the original score of the nodes in the tree. If both are equal then the complete binary tree is not yet.

Please tell me if the approach is right. Thanks.

This question is the same as this one . But I want to test my method here.

Edit: The algorithm is verified by @ Boris Strandjev below. I felt that this is the simplest algorithm to implement some of the algorithms available on the network. Sincere apologies if you do not agree with my statement.

Answer 1

Your algorithm should solve the problem.

What you do with BFS is completely equivalent to drawing a tree and then tracking nodes with your finger from top to bottom and left-to-right. The first time you cannot continue, you stop tracking with your finger. If you have not counted all the nodes, the structure is clearly not expected.