//Definition of the node
class BinaryTreeNode
{
    //Instance Variable
    BinaryTreeNode left;
    int data;
    BinaryTreeNode right;
    //Constructor
    public BinaryTreeNode(int data)
    {
        this.data=data;
        left=null;
        right=null;
    }
}
//Definition of Binary Tree
public class BinaryTree
{
    //Instance variable
    protected BinaryTreeNode root;
    //Instance method and constructors
    public BinaryTree()
    //default constructor
    //postcondition:root=null
    {
        //write the method definition here
        root=null;
    }
    public void destroyTree()
    //method to destroy the binary tree
    //postcondition:root=null
    {
        root=null;
        System.gc();

    }
    public Boolean isEmpty()
    //method to determine whether the binary tree is empty.
    //postcondition:Returns true if binary tree is empty, false
    //otherwise
    {
        return(root==null);
    }
    public int treeHeight()
    //method to determine the height of the binary tree.
    //postcondition:the height of the binary tree is returned
    {
        return height(root);
    }

    private int height(BinaryTreeNode root){
        if(root == null)
            return 0;
        else
            return 1 + max(height(root.left),height(root.right));
    }
    private int max(int l,int r){
        if(l>r){
            return l;
        }
        else{
            return r;
        }
    }

    public void insertNode(int item)
    //method to insert node in the binary tree.
    //postcondition: A node is created and inserted in the binary tree.
    {
        if(root==null){
            root=new BinaryTreeNode(item);
        }
        else{
            root=insertNode(item,root);
        }
    }

    private BinaryTreeNode insertNode(int item,BinaryTreeNode root)
    {
        if(root==null){
            root=new BinaryTreeNode(item);
        }
        else if(item<root.data){
                root.left=insertNode(item,root.left);
        }
        else if(item>root.data){
                root.right=insertNode(item,root.right);

        }
        return root;
    }
    public void inorderTraversal()
    //method to do an inorder traversal of the binary tree
    //postcondition: the nodes of the binary tree are output in the
    //inorder sequence
    {
        inorderTraversal(root);
        System.out.println();
    }
    private void inorderTraversal(BinaryTreeNode root){
        if(root!=null){
            inorderTraversal(root.left);
            System.out.print(root.data+" ");
            inorderTraversal(root.right);

        }
    }
    public void preorderTraversal()
    //method to do a preorder traversal of the binary tree.
    //postcondition:The nodes of the binary tree are output in the
    //preorder sequence.
    {
        preorderTraversal(root);
        System.out.println();
    }
    private void preorderTraversal(BinaryTreeNode root){
        if(root!=null){
            System.out.print(root.data+" ");
            preorderTraversal(root.left);
            preorderTraversal(root.right);

        }
    }
    public void postorderTraversal()
    //method to do a postorder traversal of the binary tree.
    //postcondition:The nodes of the binary tree are output in the
    //postorder sequence.
    {
        postorderTraversal(root);
        System.out.println();
    }
    private void postorderTraversal(BinaryTreeNode root){
        if(root!=null){
            postorderTraversal(root.left);
            postorderTraversal(root.right);
            System.out.print(root.data+" ");
        }
    }
    public int leaveCount(){
        return leaveCount(root);
    }
    private int leaveCount(BinaryTreeNode root){
        if(root==null){
            return 0;
        }
        else if(root.left==null&&root.right==null){
            return 1;
        }
        else{
            return leaveCount(root.left)+leaveCount(root.right);
        }
    }
    public int nodeCount(){
        return nodeCount(root);
    }
    public int nodeCount(BinaryTreeNode root){
        if(root==null){
            return 0;
        }
        else{
            return nodeCount(root.left)+nodeCount(root.right)+1;
        }

    }
}