Part 1 - Binary Tree with Random Add For part 1 of the assignment, you will add
ID: 3819311 • Letter: P
Question
Part 1 - Binary Tree with Random Add
For part 1 of the assignment, you will add a function to a Binary Tree Implementation. First, download and compile the code base using the instructions on my website: http://fog.ccsf.edu/~mluttrel/cs110c/BinaryNodeTreeCompilation.html
Once you are up and running, examine the add() function in BinaryNodeTree.cpp. It uses a balancedAdd() helper function to add a node, ensuring that the resulting tree remains balanced.
Instead of using balancedAdd() here, create a new function randomAdd(), which adds nodes in random places in the tree, and use that function instead. A random place should be determined by starting at the root, and traversing down the tree left or right with 50% probability each time. When you get to a point in the tree where left or right has no child, insert the node at this location.
Explanation / Answer
#include<stdio.h>
struct node
{
int data;
struct node *left;
struct node *right;
};
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;
}
int getLevel(struct node *node, int data)
{
return getLevelUtil(node,data,1);
}
struct node* newNode(int data)
{
struct node *temp = new struct node;
temp->data = data;
temp->left = NULL;
temp->right = NULL;
return temp;
}
int main()
{
struct node *root = new struct node;
int x;
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;
}