Java Program to Count the number of nodes and leaf nodes of Binary Tree

           In a Binary Tree, each node can have at most two nodes. For a binary tree to be a binary search tree (BST), the data of all the nodes in the left sub-tree of the root node should be less than or equals to the data of the root. The data of all the nodes in the right sub tree of the root node should be greater than the data of the root.

Count the total number of Nodes using recursion.

The counts in the above tree is 5.

Java Program to Count  number of nodes in Binary Tree

BSTNodeCount.java

package com.test;

class Node<T> {
      T data;
      Node<T> leftChild;
      Node<T> rightChild;
 
      public Node(T item) {
           this.data = item;
           leftChild = null;
           rightChild = null;
     }
}

public class BSTNodeCount<T> {
 
      Node<T> root;
      int count = 0;

      int getNodeCount() {

           return getNodeCount(root);
      }

      int getNodeCount(Node<T> node) {
           if (node == null) {
                return 0;
           } else {
                count = 1;
                count+= getNodeCount(node.leftChild);
                count+= getNodeCount(node.rightChild);
           }
           return count;
      }
 

      public static void main(String[] args) {
  
             BSTNodeCount<Integer> tree = new BSTNodeCount<Integer>();
             tree.root = new Node<Integer>(10);
             tree.root.leftChild = new Node<Integer>(2);
             tree.root.rightChild = new Node<Integer>(15);
  
             System.out.println("Total Number of nodes in a BST :-"+tree.getNodeCount());
      }
}

Output:-- Total Number of nodes in a BST :-3


What is Leaf Node ?

Leaf Node is a node having both left and right child nodes of it are NULL.

In the above Tree, Nodes 5, 8 and 14 doesn't have left and right child nodes. There are 3 leaf nodes in the given BST.


Java Program to Count the number Leaf Nodes in the given Binary Tree.

package com.test;

class Node<T> {
      T data;
      Node<T> leftChild;
      Node<T> rightChild;
 
      public Node(T item) {
           this.data = item;
           leftChild = null;
           rightChild = null;
     }
}
public class BSTLeafNodeCount<T> {

       Node<T> root;
       int getLeafNodeCount() {
             return getLeafNodeCount(root);
       }
 
       int getLeafNodeCount(Node<T> node) {
            if(node == null) {
                 return 0;
            } 
            if (node.leftChild == null && node.rightChild == null) {
                 return 1;
            } else {
                 return getLeafNodeCount(node.leftChild) + getLeafNodeCount(node.rightChild);
            }
       }
 
       public static void main(String[] args) {

              BSTLeafNodeCount<Integer> tree = new BSTLeafNodeCount<Integer>();
              tree.root = new Node<Integer>(1);
              tree.root.rightChild = new Node<Integer>(2);
              tree.root.leftChild = new Node<Integer>(5);
              tree.root.rightChild.leftChild = new Node<Integer>(1);
  
              System.out.println("Total Number of Leaf Nodes in a BST:-"+tree.getLeafNodeCount());
       }
}

Total Number of Leaf Nodes in a BST:-2




Related Post:--
1) Java Program to Reverse a Linked List using Recursion and Loops
2) How to iterate the TreeMap in reverse order in Java
3) Example to sort keys of TreeMap using Comparator with Custom Object
4) Java Program to Count Occurrence of Word in a Sentence
5) How to Remove duplicates from ArrayList in Java