Program to Find number of Leaf nodes and Non-Leaf nodes in a Binary Search Tree.:

class tree

{

int x;

tree left;

tree right;

}

class BTree

{

private tree t;

int lc=0,nlc=0;

BTree()

{

t=null;

}

public void insert(int v)

{

t=insert(t,v);

}

public void showLVR()

{

System.out.println("\nLVR :\n");

LVR(t);

}

tree insert(tree t, int v)

{

if(t==null)

{

t = new tree();

t.x = v;

t.left = null;

t.right = null;

}

else if(v

t.left = insert(t.left,v);

else if(v>t.x)

t.right = insert(t.right,v);

return t;

}

public void LVR(tree t)

{

if(t!=null)

{

LVR(t.left);

System.out.print("\t"+t.x);;

LVR(t.right);

}

}

int leafCount()

{

lc=0;

return leafCount(t);

}

int nonLeafCount()

{

nlc=0;

return nonLeafCount(t);

}

int leafCount(tree t)

{

if(t!=null)

{

leafCount(t.left);

if(t.left==null && t.right==null)

lc++;

leafCount(t.right);

}

return lc;

}

int nonLeafCount(tree t)

{

if(t!=null)

{

nonLeafCount(t.left);

if(t.left!=null || t.right!=null)

nlc++;

nonLeafCount(t.right);

}

return nlc;

}

}

class NodeCount

{

public static void main(String as[])

{

BTree t1=new BTree();

t1.insert(30);

t1.insert(20);

t1.insert(10);

t1.insert(40);

t1.insert(60);

t1.showLVR();

System.out.println("\nLeaf Node Count="+t1.leafCount());

System.out.println("\nNon-Leaf Node Count="+t1.nonLeafCount());

}

}

/* Output */

LVR : 10 20 30 40 60

Leaf Node Count=2

Non-Leaf Node Count=3