Assignment $4$: Binary Trees in C

The purpose of this assignment is to implement and manipulate binary trees in order to gain a deeper understanding of the structure of the binary tree, traversal algorithms and operations used on binary trees.

Instructions:

$1.$ Implement a binary tree with the following features:

$$ Define the structure Node for a tree:

typedef struct Node $\{$

int data;

$$ struct Node$*$ left; struct Node$*$ right;

$\}$ Node;

a$)$ Implement a function Node$*$ createNode $($int data$)$ that creates a new node with the given data and returns its pointer.

b$)$ Implement a function Node$*$ insertNode$($Node$*$ tree, int data$)$ that correctly inserts a node with the given data into the tree. This function should also call createNode to create the node.

c$)$ Implement a function called Node$*$ deleteNode$($Node$*$ tree, int data$)$ that correctly deletes a node from the tree. Do not balance the tree after deletion.

d$)$ Create a void inOrderTraversal $($Node$*$ tree$)$ function that traverses the tree in$-$order and prints the elements post order.

e$)$ Create a void preOrderTraversal $($Node$*$ tree$)$ function that traverses the tree preorder and prints the elements pre$-$order.

f$)$ Create an void postOrderTraversal $($Node$*$ tree$)$ function that traverses the tree post$-$order and prints the elements post$-$order.

g$)$ Write a function int calculateHeight $($Node$*$ tree$)$ to calculate the height of the binary tree.

h$)$ Write a function int nodeCount $($Node$*$ tree$)$ to count the total number of nodes in the tree

i$)$ Implement a search function int search $($Node$*$ tree, int value$)$ that checks if a value is in the tree.

j$)$ Create a function int minimum $($Node$*$ tree$)$ to find the minimum value in the tree.

k$)$ Create a function int maximum $($Node$*$ tree$)$ to find the maximum value in the tree.

$2.$ Write a main $()$ function to test your implemented functions. Create a tree by inserting nodes using the insertNode$()$ function and perform the following operations:

a$)$ Insert at least seven nodes with integer values of your choice.

b$)$ Print the tree list using inOrderTraversal, preOrderTraversal $()$ and postOrderTraversal $()$

c$)$ Call the calculateHeight $()$ and nodeCount $()$ functions and display the height and node count of the tree.

d$)$ Call the deleteNode $()$ on the minimum number, the maximum number and the middle number, and inOrderTraversal $()$ after each deletion to display the result of the deletions.

e$)$ Call the search$)$ function on an item that does not exist in the tree.

$3.$ Perform a Big O analysis of all the functions, except the main $()$ function. Explain clearly and precisely how you calculated the Big O$.$

Submission:

$1.$ Write well$-$commented and organized code. Clearly explain your algorithm, logic and purpose of each function in multi$-$line comments above each function.

$2.$ Include necessary header files and function prototypes.

$3.$ Test your program with different scenarios and edge cases to ensure its correctness.

$4.$ Proper memory management is required.

$5.$ Include a text file or a document explaining your approach and any challenges you encountered during the implementation.

$6.$ Submit a zip folder containing a single C source file named assignment. c as well as a big$-$o$-$analysis.pdf$,$ and approach.txt$$document$.$