1 Number of Levels in a Binary Tree (20 points) 1.1 Design a divide-and-conquer
ID: 3889353 • Letter: 1
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
#include<stdio.h>
/* A tree node structure */
struct node
{
int data;
struct node *left;
struct node *right;
};
/* Helper function for getLevel(). It returns level of the data if data is
present in tree, otherwise returns 0.*/
int getLevelUtil(struct node *node, int data, int level)
{
if (node == NULL)
return 0;
if (node->data == data)
return level;
int downlevel = getLevelUtil(node->left, data, level+1);
if (downlevel != 0)
return downlevel;
downlevel = getLevelUtil(node->right, data, level+1);
return downlevel;
}
/* Returns level of given data value */
int getLevel(struct node *node, int data)
{
return getLevelUtil(node,data,1);
}
/* Utility function to create a new Binary Tree node */
struct node* newNode(int data)
{
struct node *temp = new struct node;
temp->data = data;
temp->left = NULL;
temp->right = NULL;
return temp;
}
/* Driver function to test above functions */
int main()
{
struct node *root = new struct node;
int x;
/* Constructing tree given in the above figure */
root = newNode(3);
root->left = newNode(2);
root->right = newNode(5);
root->left->left = newNode(1);
root->left->right = newNode(4);
for (x = 1; x <=5; x++)
{
int level = getLevel(root, x);
if (level)
printf(" Level of %d is %d ", x, getLevel(root, x));
else
printf(" %d is not present in tree ", x);
}
getchar();
return 0;
}
Related Questions
Navigate
Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.