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).
non leaf node binary tree
Fig 1: Non leaf nodes in binary tree

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

binary tree non leaf left child
Fig 2: Non leaf 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

non leaf node right child tree
Fig 3: Non Leaf 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

non-leaf node both children tree
Fig 4: Non leaf nodes – left & right child
  • 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.
Fig 5: Non leaf nodes in binary tree

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)