- 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.
- 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.
- If current node have non null left & right node
- 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).
- 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
Download Code – Count Non Leaf nodes Binary Tree