//sep 24,  2001  linked tree testing
class TLT
{                // testing linked tree examples
      public static void main(String[] args)
     {  
      int n;
      LT tree = new LT(); 
      tree.ltTraverseInOrder();
      tree.ltTraversePreOrder();
      tree.ltTraversePostOrder();
      System.out.println( "Number of Nodes = " +tree.ltCountNodes());
      System.out.println( "Number of Zeros = " +tree.ltCountZeroNodes());
      System.out.println( "Count Item 5 gives  " +tree.ltCountItems(5));
      System.out.println( "Sum of data in all nodes  = " +tree.ltSumData());
       if (tree.ltItemInTree(5))
          System.out.println("5 in tree" );
       else
           System.out.println("5 not in tree" );
      } //main

} // TLT

///////////////////////////////////////////////////////////////////////////////////////////////////////////////

public class LT
{ 
   private TreeNode root;
   
   public LT()
   { 
      root= new TreeNode(5);
      root.left=new TreeNode(7);
      root.left.left=new TreeNode(0);
      root.left.right=new TreeNode(1);
      root.left.right.left=new TreeNode(0);
   }

   private void traversePreOrder(TreeNode tree)
    {
       if (tree!= null)
          {
          tree.displayNode();
          traversePreOrder(tree.left);
          traversePreOrder(tree.right);
          } 
    } 

   public void ltTraversePreOrder()
   {
       traversePreOrder(root);
       System.out.println(" ...PREORDER");
   }

   private void traverseInOrder(TreeNode tree)
    {
       if (tree!= null)
          {  
          traverseInOrder(tree.left);
          tree.displayNode();
          traverseInOrder(tree.right);
          } 
    } 

   public void ltTraverseInOrder()
   {
       traverseInOrder(root);
       System.out.println(" ...INORDER");
   }
 
    private void traversePostOrder(TreeNode tree)
    {
       if (tree!= null)
          {   
          traversePostOrder(tree.left);
          traversePostOrder(tree.right);
          tree.displayNode();
         }
    } 

    public void ltTraversePostOrder()
   {
       traversePostOrder(root);
       System.out.println(" ...POSTORDER");
   }

  

   private int countNodes(TreeNode tree)
   {
      if (tree == null)
          return 0;
      else
          return 1 + countNodes(tree.left)+countNodes(tree.right);
   }


 public int ltCountNodes()
   {
     return countNodes(root);
   }


   private int countZeroNodes(TreeNode tree)
   {
      if (tree == null) 
          return 0;
      else if (tree.data == 0)
          return 1 + countZeroNodes(tree.left) + countZeroNodes(tree.right);
      else
          return countZeroNodes(tree.left) + countZeroNodes(tree.right);
   }


   public int ltCountZeroNodes()
   {
        return countZeroNodes(root);
   }


   private int countItems(TreeNode tree, int item)
   {
     if (tree == null) 
        return 0;
     else if (tree.data == item)
        return 1 + countItems(tree.left, item)+countItems(tree.right, item);
     else
        return countItems(tree.left, item)+countItems(tree.right, item);
    }


    public int ltCountItems(int item)
    {
       return countItems(root, item);
    }


    private boolean itemInTree(TreeNode tree, int item)
    {
       if (tree == null) 
           return false;
       else if (tree.data == item)
           return true;
       else
          return itemInTree(tree.left, item)|| itemInTree(tree.right, item);
    }

    public boolean ltItemInTree(int item)
    { 
       return itemInTree(root, item);
    }


    private int sumData(TreeNode tree )
    {
      if (tree == null) 
	 return 0;
      else
         return  tree.data + sumData(tree.left)+ sumData(tree.right);
    }

    public int ltSumData()
    {
       return sumData(root);
    }
  
} // class LT   ...... LinkedTree class

////////////////////////////////////////////////////////////////////////////////////////////////////////////
public class TreeNode
{
  public int data;
  public TreeNode left;
  public TreeNode right;

  public TreeNode()
  {
     left=null;
     right=null;
  }

  public TreeNode(int item)
  {
    data=item;
    left=null;
    right=null;
  }

  public void displayNode()
  {
    System.out.print(data+" ");
  }
}// class TreeNode
///////////////////////////////////////////////////////////////////////////////////////////////////////////