Binary Tree

Application: Finding MAX in binary tree

You name it$...$MAX is often the goal to know. This week you will implement an algorithm for finding the maximum element in a binary tree.

Lab Assignment Objectives

Understand what a tree data structure is and how it is used.

Implement a tree package that includes a general binary tree, operations on tree and traversal.

Understand the Application

One way of solving the problem for finding the maximum element in your binary tree is to find the maximum element in the left subtree, find the maximum element in right sub tree, compare them with the root element, selecting which is giving the maximum value.

The Program Specification

Define a structure of the binary tree using a node $($which contains data$)$ and two links which points to the left and right children.

Provide a binary tree package that consists of:

Basic operations:

Insert an element into a tree

Delete an element from a tree

Search for an Element

Traverse the tree $($preorder$,$ inorder and postorder$)$

Auxiliary Operations

Find the size of the tree

Find the height of the tree

Find the maximum element in the binary tree using a recursive solution.

Testing Specification

Build the tree shown above, printing out the same tree using preorder, inorder and postorder traversals. Print out the maximum element found in the binary tree. Give the size and height of the tree.

Provide the Time and Space Complexity of your algorithm for finding the maximum element in the binary tree.

What to Turn In

You will hand in $2$ files: $1)$ your source file $($which will contain the tree package$)$ and $2)$ the demo test driver file $($which will additionally contain the commented out run of the output at your console$).$

Class source file. Use this title format for your $.$py file : yournameLab$4.$py $($Note: Use YOUR name$).$

Test driver file. Use this title format for demo $.$py file: demo$4\_$yourname.py $($Note: Use YOUR name$).$ Place a commented out copy of your program test run validation in this file after your source.

Submitting Multiple Files to an Assignment

Your lab assignment requires uploading more than one file; you should upload these $2$ files as one submission. To add more than one file, the Add Another File button is clicked to upload the two files one by one. Check to make sure that both files upload okay. When finished click Submit Assignment.