public class binaryTree
{
public binaryTree()
{
root = cursor = null;
}
public final void insert(String name, int weight)
{
if (root == null)
{
root = new Node();
root.name = name;
root.weight = weight;
root.left = root.right = null;
return;
}

cursor = root;
set_cursor(name);

if (cursor.name.equals(name))
{
System.out.print("Node already exists!!!");
System.out.print("\n");
return;
}

if (name.compareTo(cursor.name) < 0)
{
cursor.left = new Node();
cursor = cursor.left;
cursor.name = name;
cursor.weight = weight;
cursor.left = cursor.right = null;
return;
}

cursor.right = new Node();
cursor = cursor.right;
cursor.name = name;
cursor.weight = weight;
cursor.left = cursor.right = null;
}
public final void set_cursor(String x)
{
if (cursor.name.equals(x))
{
return;
}

if (x.compareTo(cursor.name) < 0 && cursor.left != null)
{
cursor = cursor.left;
set_cursor(x);
}

if (x.compareTo(cursor.name) > 0 && cursor.right != null)
{
cursor = cursor.right;
set_cursor(x);
}
}
public final void print()
{
System.out.print("Preorder: ");
preorder(root);
System.out.print("\n");

System.out.print("Inorder: ");
inorder(root);
System.out.print("\n");

System.out.print("Postorder: ");
postorder(root);
System.out.print("\n");
System.out.print("\n");
}

public static class Node
{
public String name;
public int weight;
public Node left;
public Node right;
}
public Node root;
public Node cursor;

public final void preorder(Node p)
{
if (p != null)
{
System.out.print(p.name);
System.out.print(' ');
preorder(p.left);
preorder(p.right);
}
}
public final void inorder(Node p)
{
if (p != null)
{
inorder(p.left);
System.out.print(p.name);
System.out.print(' ');
inorder(p.right);
}
}
public final void postorder(Node p)
{
if (p != null)
{
postorder(p.left);
postorder(p.right);
System.out.print(p.name);
System.out.print(' ');
}
}
public final int findHeight(Node p)
{
if (p.left == null && p.right == null)
{
return 0;
}
else
{
if (p.left != null)
{
left = findHeight(p.left);
}
if (p.right != null)
{
right = findHeight(p.right);
}

if (left > right)
{
h = 1 + left;
}
else
{
h = 1 + right;
}
}
return h;
}
public final int findLeaves(Node p)
{
if (p == null)
{
return 0;
}
if (p.left == null && p.right == null)
{
return 1;
}
else
{
return findLeaves(p.left) + findLeaves(p.right);
}
}
public final int search(String name)
{
int weight = 0;
cursor = root;

while (cursor != null)
{
if (cursor.name.equals(name))
{
return cursor.weight;
}

else if (name.compareTo(cursor.name) < 0)
{
cursor = cursor.left;
}

else
{
cursor = cursor.right;
}
}

System.out.print("Could not find ");
System.out.print(name);
System.out.print("\n");
System.out.print("\n");
return 0;
}
public final int lowestWeight(Node p)
{
if (p != null)
{
if (p.weight < small)
{
small = p.weight;
}
lowestWeight(p.left);
lowestWeight(p.right);
}

return small;
}
public final String firstName()
{
String first = "";
cursor = root;

if (root == null)
{
System.out.print("Tree is empty!!!");
return first;
}

else
{
while (cursor.left != null)
{
cursor = cursor.left;
}

first = cursor.name;
return first;
}
}
public int small;
public int left;
public int right;
public int h;
}