Task 2

Write necessary recursive function to traverse and print the above binary tree in

Preorder

Inorder

Postorder

Level Order Traversal

Task 3

Write function that will return

number of nodes of a given binary tree.

number of terminal (leaf ) nodes of a given binary tree.

number of nodes that contain odd number as their data field of a given binary tree.

The height or depth of a tree is defined to be the maximum level of any node in the tree. (depth=the longest path from root to any leaf node). Write a function that will return height of a given binary tree.

Binary search tree class:

Using following code snippeds complete the Binary Search Tree class implementation The textbook and lecture notes should present examples of the code necessary to complete this lab.

public class BTNode{

public T data;

public BTNode lchild;

public BTNode rchild;

public BTNode (T dat){data=dat;lchild=rchild=null}

}

class BinarySearchTree{

private BTNode root;

public BinarySearchTree() //

public void insert(T data);

public bool search( T key);

public void delete(T key);

public void inOrder()const;

public void postOrder()const;

.

Implement binary search tree class using above code sinipped Write a constructor and the insert() method. Your insert method should check for an empty root node and construct a root node if necessary. If the root node already exists, then you should call insert on the root node. To do this, you will need to implement a recursive version of insert.

Implement the printPreOrder(), printInOrder() and printPostOrder() methods. The best strategy for this is to implement simple versions of these methods in your binary search tree class. Then implement a recursive version of these methods in the MyTreeNode class. The methods in the your binary search tree class should only call the Node version on the root node, if it exists. Also implement a test program class with a main method that inserts a few objects into your binary search tree class and then prints the data in the appropriate order.

Implement the search() method. The lookup method should return true if the object is contained in the tree and return false otherwise. Modify your insert() method so as to prevent duplicate items (only insert an item if lookup() returns false). Modify your test program to demonstrate that the lookup method works.

Implement delete() method. The delete method should do nothing if the item is not found in the tree. If the item is found then it should modify the tree to remove the item. Recall that there are three cases. (Be sure to modify your main test program to illustrate that your delete method works for all three cases.)

If the item to be deleted is a leaf on the tree, delete it simply by setting the parent's reference to null.

If the item to be deleted has a single child, then delete it simply by setting the parent's reference to the single child.

If the item to be deleted has two children, then you need to

find the leftmost member of the right child.

Replace the node's data item with the data item found

Delete the node that contained the found data item (which itself can have at most one child).

Task 1: Build the following binacy tcee in java enxiconoent(10p)