Count non-leaf nodes (left & right child) in binary tree (java/ non-recursive/example)

• Given a binary tree, calculate non-leaves having left & right child nodes in a binary tree.
  • Count non leaf nodes having both children.
• We will iterate the binary tree using level order traversal or breadth first search (BFS) traversal.
• We have already discussed:
  • Count non leaf nodes in a binary tree having one child (Either left child or right child).
  • Count non leaf nodes in a binary tree (having one child or both children).

Examples: Count non leaf nodes in a binary tree

Example 1: Number of non leaf nodes in binary tree (left & right children).

Given a binary tree shown in Fig 1, calculate the number of non leaf nodes having left & right child nodes.

• Traverse the binary tree using level order traversal algorithm.
• At each node check the reference of left & right node.
  • If current node have non null left & right node
    • Increment the count of leaf nodes.
  • Else, keep on traversing the binary tree.
• We will have following conditional statement to cater this case.

  if( node.left != null && node.right != null) {
    nNonLeaves++;    
   }  

Example 2:  Count non leaf nodes having left & right child (Fig 2).

• Traverse binary tree using breadth first search.
• Declare a variable nLeaves = 0
• During iteration check, current node has both left & right child.
  • nLeaves ++ (if nodes have both left & right child).
• At the end of iteration, we will number of non leaf nodes having left & right child node.
• Number of non leaf nodes of binary tree is 5.

Time complexity of algorithm is O(n).

Program – count non leaf nodes in a binary tree using java

1.) CountNonLeafTwoChildren class:

• CountNonLeafTwoChildren class is responsible to calculate the number of non leaf nodes in a binary tree.

package org.learn.Question;

import java.util.LinkedList;
import java.util.Queue;

public class CountNonLeafNodes {
 public static int countNonLeafNodes(Node root) {
  if (root == null) {
   System.out.println("Tree is empty");
   return -1;
  }
  int nNonLeaves = 0;
  Queue<Node> queue = new LinkedList<Node>();
  queue.offer(root);

  while (!queue.isEmpty()) {
   Node node = queue.poll();

   if (node.left != null && node.right != null) {
    nNonLeaves++;
   }
   if (node.left != null) {
    queue.offer(node.left);
   }
   if (node.right != null) {
    queue.offer(node.right);
   }
  }
  System.out.println("Number of non-leaf nodes : " + nNonLeaves);
  return nNonLeaves;
 }
}

2.) Node class:

• Node class represents the nodes of a binary tree.

 package org.learn.Question;

public class Node {
 public int data;
 public Node left;
 public Node right;

 public Node(int num) {
  this.data = num;
  this.left = null;
  this.right = null;
 }

 public Node() {
  this.left = null;
  this.right = null;
 }
 public static Node createNode(int number) {
  return new Node(number);
 }
}

3.) App Class:

• We are creating a binary tree in main method.
• We are calling CountNonLeafTwoChildren class, to calculate number of non leaf nodes using level order traversal.

package org.learn.Client;

import org.learn.Question.CountNonLeafNodes;
import org.learn.Question.Node;

public class App {
 public static void main(String[] args) {
  // root level 0
  Node A = Node.createNode(55);
  // Level 1
  Node B = Node.createNode(50);
  Node C = Node.createNode(40);
  // Level 2
  Node D = Node.createNode(25);
  Node E = Node.createNode(80);
  Node F = Node.createNode(45);
  Node G = Node.createNode(90);
  // Level 3
  Node H = Node.createNode(10);
  Node I = Node.createNode(35);
  Node J = Node.createNode(65);
  Node K = Node.createNode(75);

  // connect Level 0 and 1
  A.left = B;
  A.right = C;
  // connect level 1 and level 2
  B.left = D;
  B.right = E;
  C.left = F;
  C.right = G;
  // connect level 2 and level 3
  F.left = H;
  F.right = I;
  G.left = J;
  G.right = K;

  CountNonLeafNodes.countNonLeafNodes(A);
 }
}

Output – count non leaf nodes having left & right child nodes in java

Number of non-leaf nodes : 5

Download Code – Count Non Leaf nodes Binary Tree