Find number of nodes in a complete Binary Tree
All Answers
total answers (1)
Severity: 8192
Message: str_replace(): Passing null to parameter #3 ($subject) of type array|string is deprecated
Filename: libraries/Filtered_db.php
Line Number: 23
total answers (1)
In a complete binary tree every level, except possibly the last, is completely filled, and all nodes in the last level are as far left as possible. A complete Binary Tree can have between 1 and 2h nodes inclusive at the last level h.
So, the properties of complete Binary tree is:
Now to find the number of nodes we can solve in two ways.
1) Naïve approach in O(n)
We can find the number of nodes recursively like for any binary tree.
The number of nodes in the tree= 1+ Number of nodes in the left subtree + Number of nodes in the right subtree. Below is the definition of the recursive function:
C++ Implementation:
Output:
2) Efficient method using complete binary tree properties
We can count the total number of nodes using complete tree properties:
Say, the total number of nodes is n
And the height of the complete binary tree is: h
Then it’s guaranteed that all levels up to height h-1 is completed which means has 2h-1 number of nodes up to the last level. At the last level say there r k number of nodes which are as left as much possible. So, we total no of nodes n= k+ 2h-1
So, we need to find two things:
Height of the tree can be found in O(Log2n) time and we can find k also in logarithmic time complexity using the fact that all the nodes at last level lies as left as far possible.
The algorithm is like below:
So over all time complexity is O(logn) (to find height and number of nodes in all levels except the last one)+O(logn)2 (to find number of nodes in the last level)
C++ Implementation:
Output:
need an explanation for this answer? contact us directly to get an explanation for this answer