Design a divide-and-conquer algorithm for computing the number of levels in a CO

Question

Design a divide-and-conquer algorithm for computing the number of levels in a COMPLETE binary tree. In particular, the algorithm should return 0 and 1 for the empty and single-node trees respectively. Please provide the pseudocode for your algorithm. What is the running time of your algorithm in the worst case using O) notation? (A complete binary tree refers to the type of binary trees where every level except the last level is completely filled and all the nodes are left justified. An example of the complete binary tree is shown below.) H IJKL

Explanation / Answer

Given the tree is complete binary. We need to find out the number of levels in this completely binary tree.

FUNCTION COUNT_LEVELS(NODE N)
   //If node is null, it's level is 0
   IF N == NULL
       RETURN 0
   //Answer will be 1 + maximum levels of left and right subtrees
   RETURN 1+MAX(COUNT_LEVELS(LEFT(N)), COUNT_LEVELS(RIGHT(N)))
  
The binary tree is complete binary tree. It contains N nodes. To find the number of levels in this binary tree we are iterating through all the nodes of the tree (Left and Right subtree of each node). So, complexity is O(N)

Related Questions

Navigate

• Browse (All)
• Browse D
• Subjects

---

---

Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.