You are required to implement insert and search functionalities on a binary search tree. To insert a node, you start with the root not and go down to find a location to insert the node. The insertion happens only at a NULL reference. In this project, you assume the null reference is . If the root is empty, then you create a memory block and point the root to the newly created location. If the root is not empty, then you find the next location (left reference or right reference) to insert. When inserting a node, the parent reference of the new node and child reference of the parent node should be updated with their appropriate values. Searching a node is a recursive subroutine call to find an element at a node.
The first subroutine is used to find the next available bock of memory. The block allocation field of each block determines if a block is used to store a data or not. If the allocation field is then the block is empty. If the block allocation field is 0, then the block is allocated. In this subroutine, the code iterates over the set of allocated memories and find a block that is empty and returns the address of the block. If the code does not find any memory, it is going to return as the address. You have to use the stack to return the address of the available block.
The second subroutine inserts a node to the tree. This subroutine accepts a data element as a parameter through the stack. This subroutine call the first subroutine to find a memory location to create a node. If the memory location is valid, create a node and updated the reference to create a tree structure. Then display a message saying the node is added to the tree. If the memory location is invalid, then display a message saying that there is a memory out of bounds exception. This method does not return any value.