-->

Count number of leaf nodes in a binary tree

Posted by Admin on
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 :

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.

Implementation  :

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);
       }
}


Please comment if you like the above post or find any mistake.


No comments:

Post a Comment