1 Number of Levels in a Binary Tree (20 points) 1.1 Design a divide-and-conquer

Question

1 Number of Levels in a Binary Tree (20 points) 1.1 Design a divide-and-conquer algorithm for computing the number of levels in a binary tree. In par ticular, 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? 1.2 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.) Figure 1: An Example of Complete Binary Tree.

Explanation / Answer

*************************Q1**********Algorithm************************

numberOfLevels()

     if tree is empty; return 0;

     if tree size==1; return 1;

    else

            1. compute numberOfLayers in left subtree;

                                    call numberOfLayers(tree.left);

            2. compute numberOfLayers in right subtree;

                                   call numberOfLayers(tree.right);

          3. calculate max height of both left and right subtrees and add one for current node i.e.

                                 number_of_layers=Max(maxOfLeftSubtree, maxOfRightSubtree)+1;

              return number_of_layers;

***********************Q1*****time complexity*********************

if not a proper binary tree then time complexity can be as much as O(n) in worst case; in case where all the elments inserted are in increasing or decreasing order, as it will be just like an array in the form of tree

ex. 1--- > 2--- > 4--- > 5--- > 31--- > 34--- > 41--- > 54--- >213 , this tree will be one side, all elements will be in right subtree of every node so time complexity O(n), as we have to traverse all the elements

**********************************Q2***************Algorithm*************************

above algorithm, i.e. algorithm given for question 1 will work for this question too. just remove part for calculating height of right substree, i.e just calculate height of left subtree as we know that left subtree is max height(property, also see in picture)

alternative algorithm is:   (but this is not divide and concurr, as no need and not possible, if forced to use divide and concurr use above algorithm only) else use following;

numberOfLayers()

     if size==0;return 0;

     if size==1; return 1;

       int number_of_layers=0;

      while leftNode is not equal to null      

               number_of_layers++;

    return number_of_layers+1;

*************************************Time complexity************************

time complexity will be O(Log(n)) in this case as only half side needs to be traversed every time when we reach on particular node, i.e, it gets half every time we get to next node, 1/2 * 1/2 * 1/2 * .........   =log(n)

Related Questions

Navigate

• Browse (All)
• Browse 1
• Subjects

---

---

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