Mumbai University > Computer Engineering > Sem 3 > Data Structures

Marks: 10M

Years: Dec 2015

import java.io.*;
class Node
{
    int data;
    Node left, right;
    boolean rt;
}
class BT
{
    private Node root;
    public BT()
    {
        root=null;
    }
    void insert(int x)
    {
        Node p,follow;
        Node ptr=new Node(x);
        if(ptr==null)
        {
            System.out.println("Required Node not found.");
        }
        ptr.left=ptr.right=null;
        if(root==null)
        {
            root=ptr;
        }
        else
        {
            p=root;
            follow=null;
            while(p!=null)
            {
                follow=p;
                if(ptr.data<p.data)
                {
                    p=p.left;
                }
                else
                    p=p.right;
            }
            if(ptr.data<follow.data)
                follow.left=ptr;
            else
                follow.right=ptr;
        }
    }
    void callLeafCount()
    {
        lCount=0;
        leafCount(root);
        System.out.println("Total no. of leaf nodes:"+lCount);
    }
    void leafCount(Node root)
    {
        if(root!=null)
        {
            leafCount(root.left);
            if(root.left==null && root.right==null)
            {
                lCount++;
                System.out.println(root.data);
            }
            leafCount(root.right);
        }
    }
    void callBranchCount()
    {
        bCount=0;
        branchCount(root);
        System.out.println("Total no. of branch nodes:"+bCount);
    }
    void branchCount(Node root)
    {
        if(root!=null)
        {
            branchCount(root.left);
            nCount++;
            branchCount(root.right);
        }
    }
}
class BTMain
{
    public static void main(String args[]) throws IOException
    {
        BufferedReader br=new BufferedReader(new InputStreamReader(System.in));
        int x,k,choice;
        BT t=new BT();
        do
        {
            System.out.println("Menu:");
            System.out.println("1.Insert");
            System.out.println("2.Leaf Count");
            System.out.println("3.Branch Count");
            System.out.println("4.Exit");
            System.out.println("Enter your choice:");
            ch=Integer.parseInt(br.readLine());
            switch(ch)
            {
                case 1:
                    System.out.println("Enter the value of new Node:");
                    x=Integer.parseInt(br.readLine());
                    t.insert(x);
                    break;
                case 2:
                    t.callLeafCount();
                    break;
                case 3:
                    t.callBranchCount();
                    break;
                case 4:
                    break;
            }   }

    }
}