Q: 3. A) Given the program trace the insertion function to complete the tree below.

(10 pts)

18

#include

#include

struct node {

int data;

struct node *leftChild;

struct node *rightChild;

};

struct node *root = NULL;

void insert(int data) {

struct node *tempNode = (struct node*) malloc(sizeof(struct node));

struct node *current;

struct node *parent;

tempNode->data = data;

tempNode->leftChild = NULL;

tempNode->rightChild = NULL;

//if tree is empty

if(root == NULL) {

root = tempNode;

} else {

current = root;

parent = NULL;

while(1) {

parent = current;

//go to left of the tree

if(data < parent->data) {

current = current->leftChild;

//insert to the left

if(current == NULL) {

parent->leftChild = tempNode;

return;

}

} //go to right of the tree

else {

current = current->rightChild;

//insert to the right

if(current == NULL) {

parent->rightChild = tempNode;

return;

}

}

}

}

}

struct node* search(int data) {

struct node *current = root;

printf("Visiting elements: ");

while(current->data != data) {

if(current != NULL)

printf("%d ",current->data);

//go to left tree

if(current->data > data) {

current = current->leftChild;

}

//else go to right tree

else {

current = current->rightChild;

}

//not found

if(current == NULL) {

return NULL;

}

}

return current;

}

void pre_order_traversal(struct node* root) {

if(root != NULL) {

printf("%d ",root->data);

pre_order_traversal(root->leftChild);

pre_order_traversal(root->rightChild);

}

}

void inorder_traversal(struct node* root) {

if(root != NULL) {

inorder_traversal(root->leftChild);

printf("%d ",root->data);

inorder_traversal(root->rightChild);

}

}

void post_order_traversal(struct node* root) {

if(root != NULL) {

post_order_traversal(root->leftChild);

post_order_traversal(root->rightChild);

printf("%d ", root->data);

}

}

int main() {

int i;

int array[7] = { 18, 27, 42, 31, 19, 10, 35, 14 };

for(i = 0; i < 7; i++)

insert(array[i]);

i = 31;

struct node * temp = search(i);

if(temp != NULL) {

printf("[%d] Element found.", temp->data);

printf(" ");

}else {

printf("[ x ] Element not found (%d). ", i);

}

i = 15;

temp = search(i);

if(temp != NULL) {

printf("[%d] Element found.", temp->data);

printf(" ");

}else {

printf("[ x ] Element not found (%d). ", i);

}

printf(" Preorder traversal: ");

pre_order_traversal(root);

printf(" Inorder traversal: ");

inorder_traversal(root);

printf(" Post order traversal: ");

post_order_traversal(root);

return 0;

}

Q: 3. B) After you complete the tree trace search algorithm to find 31 and 15. You should print which nodes were visited to find or search for them. (15 pts)

Q: 3. C) Trace the postorder traversal, preorder traversal and inorder traversal functions to print the postorder, preorder and inorder outputs. (15 pts)

c programming