Tree Implementations Write a program to: a) Build a fully left skewed binary sea

ID: 3821652 • Letter: T

Question

Tree Implementations

Write a program to: a) Build a fully left skewed binary search tree (BST) with 26 levels and output the corresponding complete balanced BST. You must demonstrate through your program the insertion of elements starting with an empty BST and then implement the balance operation to convert it into a balanced BST. You can choose numeric (1, 2, 3... 26) or alphabetic (A, B, C..., Z) data values to build your BST. You need to compute midpoints for each division. You need to perform the divisions until log2 26 numbers of iterations. Your implementation should: Input the data values and build the unbalanced BST Build the BST for the best height (balanced tree) Output the balanced BST Compute the system time for both the tree data structures (balanced and unbalanced) b) Implement Depth First Traversal, Breadth First Traversal and Best First Traversal (based on priority maximum value in a level) for both the unbalanced and balanced search trees. Your implementation should: Output the traversal order Compute the system time for all traversals both the balanced and unbalanced trees.

Explanation / Answer

// C program to demonstrate insert operation in binary search tree

#include<stdio.h>

#include<stdlib.h>

struct node

{

int key;

struct node *left, *right;

};

// A utility function to create a new BST 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;

}

// A utility function to do inorder traversal of BST

void inorder(struct node *root)

{

if (root != NULL)

{

inorder(root->left);

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

inorder(root->right);

}

/* A utility function to insert a new node with given key in BST */

struct node* insert(struct node* node, int key)

{

/* If the tree is empty, return a new node */

if (node == NULL) return newNode(key);

/* Otherwise, recur down the tree */

if (key < node->key)

node->left = insert(node->left, key);

else if (key > node->key)

node->right = insert(node->right, key);

/* return the (unchanged) node pointer */

return node;

}

// Driver Program to test above functions

int main()

{

/* Let us create following BST

30 70

/ /

20 40 60 80 */

struct node *root = NULL;

root = insert(root, 50);

insert(root, 30);

insert(root, 20);

insert(root, 40);

insert(root, 70);

insert(root, 60);

insert(root, 80);

// print inoder traversal of the BST

inorder(root);

return 0;

}