Count non-leaves (left & right child) - binary tree BFS 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.

non leaf node binary tree — Fig 1: Non leaf node (left & right child)

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).

non leaf node non recursive — Fig 2: Count non leaf nodes having left & right child

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

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

Examples: Count non leaf nodes in a binary tree

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

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

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

1.) CountNonLeafTwoChildren class:

2.) Node class:

3.) App Class:

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

Download Code – Count Non Leaf nodes Binary Tree

Examples: Count non leaf nodes in a binary tree

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

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

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

1.) CountNonLeafTwoChildren class:

2.) Node class:

3.) App Class:

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

You may also like: