Please provide an explanation for your answer. It\'s more important that I under

Question

Please provide an explanation for your answer. It's more important that I understand it then get the right answer.

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.) HIL Figure 1: An Example of Complete Binary Tree

Explanation / Answer

Answering part 1.1 and 1.2 together,

Principle:

For this algorithm we define a single function H(x); which determines the height of a binary tree.

H(x) = MAX[H(x.left), H(x.right)] + 1

this is a recursive function, with a base condition as follows,

H(x)=0 if x=NULL,

x.left and x.right denotes the left and right subtree of tree x.

Pseudocode:

getH(Tree){ //'getH' is the H(x) function, 'Tree' is the given input tree

if(Tree == NULL){ //checking base condition H(x)=0 if x=NULL

return 0;} //returning base condition value

else{

return getMAX(getH(Tree.Left), getH(Tree.Right))+1;}   /*getMAX is function to find maximum of two numbers; Here also we add 1 with maximum which counts for the level of root node, if there is only root node then it returns 1.*/

Explanation:

Related Questions

Navigate

• Browse (All)
• Browse P
• Subjects

---

---

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