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 children. For a Binary Tree to be a Binary Search Tree (BST), all nodes in the left subtree of the root must have values less than or equal to the root’s value, and all nodes in the right subtree must have values greater than the root’s value.

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 ?

A leaf node is a node whose left and right child nodes are both 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