Write a program to count the number of leaf nodes in a binary tree . For example if we have the following tree then it must return 3(as it has three leaf node 1,3 and 5).
Algorihtms :
1) Traverse the left node .
2) Traverse th right node .
3) If the node is null then return 0.
4) If both the child node are 0 then it means it is leaf node .Hence return 1 .
See the following countLeafnode() method :
Visualization of above Algorithm (Working of above method )
Implementation :
Please comment if you like the above post or find any mistake.
Algorihtms :
1) Traverse the left node .
2) Traverse th right node .
3) If the node is null then return 0.
4) If both the child node are 0 then it means it is leaf node .Hence return 1 .
See the following countLeafnode() method :
public static int countLeafnode(BSTNode p)
{
if(p==null)
{
return 0;
}
//if left and right
both child of a node are null it means it is leaf node
if(p.left==null && p.right==null)
{
return 1;
}
return countleafnode(p.left)+countleafnode(p.right);
}
Visualization of above Algorithm (Working of above method )
When the both the
child of a node are null then it means it a leaf nodes hence it will return 1.
class BSTNode {
int data;
BSTNode right;
BSTNode left;
BSTNode(int d) {
data = d;
}
}
public class LeafNode {
public static void main(String args[])
{
BSTNode root =
new BSTNode(4);
root.left = new BSTNode(2);
root.right = new BSTNode(5);
root.left.left = new BSTNode(1);
root.left.right = new BSTNode(3);
int n = countLeafnode(root);
System.out.println(n);
}
public static int
countLeafnode(BSTNode p)
{
if(p==null)
{
return 0;
}
//if left and right
both child of a node are null it means it is leaf node
if(p.left==null && p.right==null)
{
return 1;
}
return countLeafnode(p.left)+countLeafnode(p.right);
}
}
No comments:
Post a Comment