Okay so I am supposed to print the level of the leaf with the largest level and
ID: 3858054 • Letter: O
Question
Okay so I am supposed to print the level of the leaf with the largest level and the level of the leaf with the smallest level. Repeat this process 50 times. Print out a table with a count of how many of the 50 runs resulted in a difference between the maximum and minimum leaf level of 0, 1, 2, 3, and so on. I have written the following code so far but each time I get my output with each level difference with a #Runs of either 1 or 2. Can someone take a look at this and tell me what I am doing wrong?
The output should be along the lines of:
Level Difference # Runs
0 3
1 5
2 6
3 1
4 0
5 3
. .
. .
. .
#include<stdio.h>
#include<stdlib.h>
#include<time.h>
struct node
{
int key;
struct node* left;
struct node* right;
}node;
struct node *newNode(int item)
{
struct node *temp = (struct node *)malloc(sizeof(struct node));
temp->key = item;
temp->left = temp->right = NULL;
return temp;
}
void inorder(struct node *root)
{
if (root != NULL)
{
inorder(root->left);
inorder(root->right);
}
}
struct node* insert(struct node* node, int key)
{
if (node == NULL)
{
return newNode(key);
}
if (key < node->key)
{
node->left = insert(node->left, key);
}
else if (key > node->key)
{
node->right = insert(node->right, key);
}
return node;
}
int generateRandom()
{
return rand() % 1000 + 1;
}
int maxLevel(struct node *root,int level)
{
if (root == NULL)
{
return 0;
}
if (root->left==NULL && root->right==NULL)
{
return level;
}
return max(maxLevel(root->left, level+1), maxLevel(root->right, level+1));
}
int minLevel(struct node *root,int level)
{
if (root == NULL)
{
return 0;
}
if (root->left==NULL && root->right==NULL)
{
return level;
}
return level;
}
int max(int x, int y)
{
return (x > y)? x : y;
}
int min(int x, int y)
{
return (x < y)? x : y ;
}
int main()
{
struct node *root = NULL;
int arr[101]={0};
int i=0, x, maxL, minL, diffL, j=0, k=0;
for(j=0; j<50; j++)
{
srand(time(NULL));
for(i=0;i<100;i++)
{
x=generateRandom();
if(i==0)
{
root=insert(root, x);
}
else
{
insert(root,x);
}
}
maxL=maxLevel(root,0);
minL=minLevel(root,0);
diffL=maxL-minL;
arr[j]=arr[diffL]+1;
}
printf("Largest Level Leaf: %d ", maxL);
printf("Smallest Level Leaf: %d ", minL);
printf("Level difference # Runs ");
for(k=0;k<50;k++)
{
printf("%d %d ",k, arr[k]);
}
return 0;
}
Explanation / Answer
srand should not be used inside a loop as it generates same random numbers in each iteration. It should be used as shown below in the code.
Also the minLevel function was always giving 0, now it's correct.
Also, arr[j]=arr[diffL]+1; should be arr[diffL]=arr[diffL]+1; to store the count of how many times same difference gaenerated.
Code:
#include<stdio.h>
#include<stdlib.h>
#include<time.h>
struct node
{
int key;
struct node* left;
struct node* right;
}node;
struct node *newNode(int item)
{
struct node *temp = (struct node *)malloc(sizeof(struct node));
temp->key = item;
temp->left = temp->right = NULL;
return temp;
}
void inorder(struct node *root)
{
if (root != NULL)
{
inorder(root->left);
inorder(root->right);
}
}
struct node* insert(struct node* node, int key)
{
if (node == NULL)
{
return newNode(key);
}
if (key < node->key)
{
node->left = insert(node->left, key);
}
else if (key > node->key)
{
node->right = insert(node->right, key);
}
return node;
}
int generateRandom()
{
return rand() % 1000 + 1;
}
int max(int x, int y)
{
return (x > y)? x : y;
}
int min(int x, int y)
{
return (x < y)? x : y ;
}
int maxLevel(struct node *root)
{
if (root == NULL)
{
return 0;
}
return max(maxLevel(root->left)+1, maxLevel(root->right)+1);
}
int minLevel(struct node *root)
{
if (root == NULL)
{
return 0;
}
if (root->left==NULL && root->right==NULL)
{
return 1;
}
// If left subtree is NULL, recur for right subtree
if (!root->left)
return minLevel(root->right) + 1;
// If right subtree is NULL, recur for right subtree
if (!root->right)
return minLevel(root->left) + 1;
return min(minLevel(root->left), minLevel(root->right)) + 1;
}
int main()
{
struct node *root;
int arr[101]={0};
int i=0, x, maxL, minL, diffL, j=0, k=0;
srand(time(0));
for(j=0; j<50; j++)
{
root = NULL;
for(i=0;i<100;i++)
{
x=generateRandom();
if(i==0)
{
root=insert(root, x);
}
else
{
insert(root,x);
}
}
maxL=maxLevel(root);
minL=minLevel(root);
// printf("Largest Level Leaf: %d ", maxL);
// printf("Smallest Level Leaf: %d ", minL);
diffL=maxL-minL;
arr[diffL]=arr[diffL]+1;
}
printf("Level difference # Runs ");
for(k=0;k<50;k++)
{
printf("%d %d ",k, arr[k]);
}
return 0;
}
Related Questions
drjack9650@gmail.com
Navigate
Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.