//Binary tree
class Node
{   Node left, right;
    char data;
}//class node
public class BinaryTree
{   
//*************************
void displayPreorder(Node root)
{   if(root!=null)
        {   System.out.println(root.data);
            displayPreorder(root.left);
            displayPreorder(root.right);
        }
}//display Preorder
//*************************
void displayInorder(Node root)
{   if(root!=null)
    {   displayInorder(root.left);
        System.out.println(root.data);
        displayInorder(root.right);
    }
}//display Inorder
//*************************
void displayPostorder(Node root)
{   if(root!=null)
    {   displayPostorder(root.left);
        displayPostorder(root.right);
        System.out.println(root.data);
    }
}//display Postorder
//*************************
Node createRoot(char item)
{   Node root=new Node();
    root.data=item;
    root.left=root.right=null;
    return root;
}//createRoot
//*************************
void create(Node root, char item, char after, char pos)
{   if(root!=null)
    {   if(after==root.data)
        {   Node ptr=new Node();
            ptr.data=item;
            ptr.left=ptr.right=null;
            if(pos=='l')
                root.left=ptr;
            else
                root.right=ptr;
        }
        create(root.left, item,after,pos);
        create(root.right,item,after,pos);
    }//if(root!=null)
}//create
//*************************
int countNodes(Node root)
{   if(root!=null)
    {   return 1+countNodes(root.left)+countNodes(root.right);
    }
    else
    {   return 0;
    }
}//countNodes
//*************************
public static void main(String args[])
{   BinaryTree bt=new BinaryTree();
    Node root;
    root=bt.createRoot('a');
    bt.create(root, 'b', 'a', 'l');
    bt.create(root, 'c', 'a', 'r');
    bt.create(root, 'd', 'b', 'l');
    bt.create(root, 'e', 'b', 'r');
    bt.create(root, 'f', 'c', 'l');
    bt.create(root, 'g', 'c', 'r');
    bt.create(root, 'h', 'f', 'l');
    bt.create(root, 'i', 'f', 'r');
    System.out.println("Preorder traversal");
    bt.displayPreorder(root);
    System.out.println("Number of nodes");
    System.out.println(bt.countNodes(root));
}//main
}//class Binary Tree