Implement the find1() and find2() in Java.

find1(k, n) // find value k in tree rooted at Node n using a while loop

find2(k, n) // find value k in tree rooted at Node n using recursion

node_count(n) // counts the nodes in the tree

node_sum(n) // sums up all the values stored at the nodes

levels(n) // returns how many levels of nodes are in the tree.

// An empty tree has 0 levels.

//=============================================

// Client Program

//

class Node_03

{

public static void main (String[] args) throws java.lang.Exception

{

//--------------------------------------------

// Build the tree

//

Node node_1 = new Node(1);

Node node_4 = new Node(4);

Node node_6 = new Node(6);

Node node_3 = new Node(3, node_1, node_4);

Node node_9 = new Node(9, node_6, null);

Node node_5 = new Node(5, node_3, node_9);

// Test Cases

System.out.println("find1(1, node_5): " + find1(1, node_5));

System.out.println("find2(1, node_5): " + find2(1, node_5) + ' ');

System.out.println("find1(4, node_5): " + find1(4, node_5));

System.out.println("find2(4, node_5): " + find1(4, node_5) + ' ');

System.out.println("find1(6, node_5): " + find1(6, node_5));

System.out.println("find2(6, node_5): " + find2(6, node_5) + ' ');

System.out.println("find1(3, node_5): " + find1(3, node_5));

System.out.println("find2(3, node_5): " + find1(3, node_5) + ' ');

System.out.println("find1(9, node_5): " + find1(9, node_5));

System.out.println("find2(9, node_5): " + find2(9, node_5) + ' ');

System.out.println("find1(5, node_5): " + find1(5, node_5));

System.out.println("find2(5, node_5): " + find1(5, node_5) + ' ');

System.out.println("find1(2, node_5): " + find1(2, node_5));

System.out.println("find2(2, node_5): " + find2(2, node_5) + ' ');

System.out.println("find1(8, node_5): " + find1(8, node_5));

System.out.println("find2(8, node_5): " + find1(8, node_5) + ' ');

System.out.println("node_count(node_5): " + node_count(node_5));

System.out.println("node_sum(node_5): " + node_sum(node_5));

System.out.println("levels(node_5): " + levels(node_5) + ' ');

// Print serialized tree

//

serial(node_5); System.out.println();

}

//--------------------------------------------

// Sertialize tree

//

//------------------------------------

static void serial(Node n)

{

if (n == null) System.out.print('-');

else

{

System.out.print(n.data + " ");

serial(n.left); System.out.print(' ');

serial(n.right);

}

}

//------------------------------------

static void in_order(Node n)

{

if(n == null) return;

in_order(n.left);

System.out.print(n.data + " ");

in_order(n.right);

}

//------------------------------------

// Iterative find, use while loop

//

static Node find1(int value, Node n)

{

return null;

}

//------------------------------------

// Recursive find.

//

static Node find2(int value, Node n)

{

return null;

}

//------------------------------------

// Count how many Nodes in the tree.

//

static int node_count(Node n)

{

return 0;

}

//------------------------------------

// Dum up the values stored at the Nodes.

//

static int node_sum(Node n)

{

return 0;

}

//------------------------------------

// How many Nodes on a path from root

// to deepest Node in the tree.

//

static int levels(Node n)

{

return 0;

}

}

//=============================================

// Define Node class

//

class Node

{

int data;

Node left;

Node right;

Node(int d, Node l, Node r)

{

data = d;

left = l;

right = r;

}

Node(int d)

{

data = d;

left = null;

right = null;

}

}

/*

Serialized tree:

5 3 1 - - 4 - - 9 6 - - -

*/