Saturday, 10 August 2013

Whether a given Binary Tree is complete or not

Whether a given Binary Tree is complete or not

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.

No comments:

Post a Comment