Whether a given Binary Tree is complete or not
algorithm, data-structures
Solution
Your algorithm should solve the problem.
What you are doing with the BFS is entirely equivalent to drawing the tree and then tracing the nodes with your finger top-down and left-right. The first time you can not continue you stop tracing with your finger. If you have not counted all the nodes then the structure is not as expected obviously.
Problem
Given a Binary Tree, write a function to check whether the given Binary Tree is Complete Binary Tree or not. A complete binary tree is a binary tree in which every level, except possibly the last, is completely filled, and all nodes are as far left as possible. source: wikipedia My approach is do BFS using queue and count the no of nodes. Run a loop till the queue is not null but break once you find one of the below condition holds good: - left node is not present for a node - left node is present but right node is not present. Now we can compare the count that we get from the above approach and the original count of the nodes in the tree. If both equal then complete binary tree else not. Please tell me whether the approach is correct or not. Thanks. This question is same as that of this. But i wan to verify my method here. Edit: The algorithm is verified by @Boris Strandjev below. I felt this is the easiest algorithm to implement out of some algorithms available in net. Sincere apologize if you do not agree with my assertion.