Count non leaf nodes in binary tree having one child node (BFS/example)

• Given a binary tree in java.
• Calculate number of non-leaves having one child node.
  • i.e. count the number of nodes in binary tree having either left or right child.
• Traverse the binary tree  non recursive algorithm.
  • level order traversal or breadth first search algorithm
• We have already discussed other flavors of current problem:
  • Count non leaf nodes in a binary tree having two children (left child & right child).
  • Count non leaf nodes in a binary tree (having one child or both children).

Examples: non leaf nodes in binary tree having one child

Example 1 – Non leaf node having left child only

• Iterate through the binary tree using BFS or level order traversal.
• Find non leaf node having left child only?
  • The node having non null left child & null right child.
• Get number of non leaf nodes in a binary (having one left child node).

The conditional statement at non leaf node is as follows.

if(nonLeafNode.left != null && nonLeafNode.right==null) {
 // Leaf node having left child only and right child is null
}

Example 2 – Non leaf node having right child only

The algorithm to count non leaf nodes in a binary tree is similar to example 1. The conditional statement at non leaf nodes is as follows:

if(nonLeafNode.left == null && nonLeafNode.right!=null) {
 // Leaf node having right child only and left child is null
}

Example 1 & Example 2 conditional statements are sufficient, to calculate number of non leaf nodes having either left or right child in a binary tree.

Example 3 – Non leaf nodes having left child or right child

• Traverse the binary tree using breadth first search algorithm (Fig 4)
• Declare a variable nNonLeaves = 0
• During iteration check, current node has left or right child only (example 1 & example 2).
  • nNonLeaves ++ (if non leaf node has left or right child only).
• At the end of iteration, we will number of non leaf nodes having one child node.
• Number of non leaf nodes of binary tree is 3.

Time complexity of algorithm is O(n).

Program: number of non leaf nodes in a binary tree – BFS.

1.) CountNonLeafNodes Class:

CountNonLeafNodes class is responsible for calculating the number of non leaf nodes having one child only using level order traversal (non recursive algorithm).

package org.learn.Question;

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

public class CountNonLeafOneChild {
 public static int countNonLeafOneChild(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) 
     || (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 in a binary tree: " + nNonLeaves);
  return nNonLeaves;
 }
}

2.) Node class:

Node Class representing 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:

• Create the binary tree.
• Invoke CountNonLeafNodes method to calculate number of leaf nodes using level order traversal algorithm.

package org.learn.Client;

import org.learn.Question.CountNonLeafOneChild;
import org.learn.Question.Node;

public class App {
 public static void main(String[] args) {
  // root level 0
  Node A = Node.createNode(60);
  // Level 1
  Node B = Node.createNode(20);
  Node C = Node.createNode(80);
  // Level 2
  Node D = Node.createNode(10);
  Node E = Node.createNode(30);
  Node F = Node.createNode(70);
  Node G = Node.createNode(90);
  // Level 3
  Node H = Node.createNode(65);
  Node I = Node.createNode(75);
  Node J = Node.createNode(95);

  // 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
  D.left = H;
  F.right = I;
  G.right = J;

  CountNonLeafOneChild.countNonLeafOneChild(A);
 }
}

Output : Number of non leaf nodes in binary tree:

Number of non-leaf nodes in a binary tree: 3

Code – Non Leaf nodes binary tree (BFS/non-recursive)