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

Yogesh

9 years ago

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