Count non leaf nodes in binary tree in java (BFS /examples)

• Given a binary tree, calculate non-leaves in a binary tree using non recursive algorithm.
• Traverse the binary tree using level order traversal or breadth first search (BFS) algorithm.
• To count non leaf nodes in  binary tree, we will virtually have following cases:
  • 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 (Either left child or right child).

Let us look into the examples to find number of non leaf nodes in binary tree using breadth first search algorithm.

Example 1: number of non leaf nodes  having left child node

• Iterate through the binary tree using BFS or level order traversal.
• Find non leaf node having non-null left child & null right child node.
• We will get number of non leaf nodes in a binary (having left child nodes).

Example 2: number of non leaf nodes  having right child node

• The algorithm to find non leaf nodes having right child is quite similar to Example 1.
• Find non leaf nodes, having null left child & non-null right child node.
• We will get number of non leaf nodes in a binary (having right child nodes).

Example 3: number of non leaf nodes having left & right child nodes

• Traverse the binary tree using level order traversal.
• Find non leaf nodes having non-null left & right child nodes.
• We will get number of non leaf nodes in a binary (having left & right child nodes).

Total number of non leaf nodes in a binary tree (Fig 5)

• Non leaf nodes having left or/and right child node.
• Non leaf node at level 0 i.e. Node A is non leaf node having both left & right child nodes.
• Non leaf nodes at level 1 i.e.Node B & Node C are non leaf nodes having left & right child nodes.
• Non leaf nodes at level 2
  • Node D & Node F are non leaf node having left & right child node respectively.
  • Node G is non leaf node having left & right children.

Time complexity of algorithm is O(n).

Program: count number of non leaf nodes in a binary tree using java

1.) CountNonLeafNodes Class:

• CountNonLeafNodes class is responsible for calculating the number of non leaf nodes in a binary tree.
• Traverse the binary using level order traversal or breadth first search non recursive algorithm.

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("Non Leaf nodes in a binary tree : " + nNonLeaves);
		return nNonLeaves;
	}
}

2.) Node class:

• Node class is representing 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 constructing the binary tree in main method.
• We are calling the method of CountNonLeafNodes  class, to calculate number of non leaf nodes.
• We will traverse binary tree using non recursive algorithm.

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(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(85);
		Node K = 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.left = J;
		G.right = K;

		CountNonLeafNodes.countNonLeafNodes(A);
	}
}

Output: number of non leaf nodes using level order traversal (java)

Non Leaf nodes in a binary tree : 6

Download Code – count non leaf nodes binary tree (BFS)