Count Non-Leaf nodes in a Binary Tree
Given a Binary tree, count the total number of non-leaf nodes in the tree
Examples:
Input :
Output :2 Explanation In the above tree only two nodes 1 and 2 are non-leaf nodes
We recursively traverse the given tree. While traversing, we count non-leaf nodes in left and right subtrees and add 1 to the result
Implementation:
C++
// CPP program to count total number of // non-leaf nodes in a binary tree #include <bits/stdc++.h> using namespace std; /* A binary tree node has data, pointer to left child and a pointer to right child */ struct Node { int data; struct Node* left; struct Node* right; }; /* Helper function that allocates a new node with the given data and NULL left and right pointers. */ struct Node* newNode( int data) { struct Node* node = new Node; node->data = data; node->left = node->right = NULL; return (node); } /* Computes the number of non-leaf nodes in a tree. */ int countNonleaf( struct Node* root) { // Base cases. if (root == NULL || (root->left == NULL && root->right == NULL)) return 0; // If root is Not NULL and its one of its // child is also not NULL return 1 + countNonleaf(root->left) + countNonleaf(root->right); } /* Driver program to test size function*/ int main() { struct Node* root = newNode(1); root->left = newNode(2); root->right = newNode(3); root->left->left = newNode(4); root->left->right = newNode(5); cout << countNonleaf(root); return 0; } |
Java
// Java program to count total number of // non-leaf nodes in a binary tree class GfG { /* A binary tree node has data, pointer to left child and a pointer to right child */ static class Node { int data; Node left; Node right; } /* Helper function that allocates a new node with the given data and NULL left and right pointers. */ static Node newNode( int data) { Node node = new Node(); node.data = data; node.left = null ; node.right = null ; return (node); } /* Computes the number of non-leaf nodes in a tree. */ static int countNonleaf(Node root) { // Base cases. if (root == null || (root.left == null && root.right == null )) return 0 ; // If root is Not NULL and its one of its // child is also not NULL return 1 + countNonleaf(root.left) + countNonleaf(root.right); } /* Driver program to test size function*/ public static void main(String[] args) { Node root = newNode( 1 ); root.left = newNode( 2 ); root.right = newNode( 3 ); root.left.left = newNode( 4 ); root.left.right = newNode( 5 ); System.out.println(countNonleaf(root)); } } |
Python3
# Python3 program to count total number # of non-leaf nodes in a binary tree # class that allocates a new node with the #given data and None left and right pointers. class newNode: def __init__( self ,data): self .data = data self .left = self .right = None # Computes the number of non-leaf # nodes in a tree. def countNonleaf(root): # Base cases. if (root = = None or (root.left = = None and root.right = = None )): return 0 # If root is Not None and its one of # its child is also not None return ( 1 + countNonleaf(root.left) + countNonleaf(root.right)) # Driver Code if __name__ = = '__main__' : root = newNode( 1 ) root.left = newNode( 2 ) root.right = newNode( 3 ) root.left.left = newNode( 4 ) root.left.right = newNode( 5 ) print (countNonleaf(root)) # This code is contributed by PranchalK |
C#
// C# program to count total number of // non-leaf nodes in a binary tree using System; class GfG { /* A binary tree node has data, pointer to left child and a pointer to right child */ class Node { public int data; public Node left; public Node right; } /* Helper function that allocates a new node with the given data and NULL left and right pointers. */ static Node newNode( int data) { Node node = new Node(); node.data = data; node.left = null ; node.right = null ; return (node); } /* Computes the number of non-leaf nodes in a tree. */ static int countNonleaf(Node root) { // Base cases. if (root == null || (root.left == null && root.right == null )) return 0; // If root is Not NULL and its one of its // child is also not NULL return 1 + countNonleaf(root.left) + countNonleaf(root.right); } /* Driver code*/ public static void Main(String[] args) { Node root = newNode(1); root.left = newNode(2); root.right = newNode(3); root.left.left = newNode(4); root.left.right = newNode(5); Console.WriteLine(countNonleaf(root)); } } // This code is contributed by PrinciRaj1992 |
Javascript
<script> // Javascript program to count total number of // non-leaf nodes in a binary tree /* A binary tree node has data, pointer to left child and a pointer to right child */ class Node { constructor(data) { this .left = null ; this .right = null ; this .data = data; } } /* Helper function that allocates a new node with the given data and NULL left and right pointers. */ function newNode(data) { let node = new Node(data); return (node); } /* Computes the number of non-leaf nodes in a tree. */ function countNonleaf(root) { // Base cases. if (root == null || (root.left == null && root.right == null )) return 0; // If root is Not NULL and its one of its // child is also not NULL return 1 + countNonleaf(root.left) + countNonleaf(root.right); } let root = newNode(1); root.left = newNode(2); root.right = newNode(3); root.left.left = newNode(4); root.left.right = newNode(5); document.write(countNonleaf(root)); // This code is contributed by mukesh07. </script> |
2
Time Complexity: O(N)
Space Complexity: If we don’t consider the size of the stack for function calls then O(1) otherwise O(h) where h is the height of the tree.
Another Approach(Iterative):
The given problem can be solved by using the Level Order Traversal.
Follow the steps below to solve the problem:
1) Create a queue(q) and initialize count variable with 0, and store the nodes in q along wise level order and iterate for next level.
2) Perform level order traversal and check if current node is a non-leaf node(have right or left any one child) then increment the count variable.
3) After completing the above steps, return count variable.
Below is the implementation of above approach:
C++
// C++ implementation to find non-leaf // count of a given Binary tree #include <bits/stdc++.h> using namespace std; // A binary tree node struct Node{ int data; struct Node* left; struct Node* right; }; // utility function to get the new node Node* newNode( int data){ Node *new_node = new Node(); new_node->data = data; new_node->left = NULL; new_node->right = NULL; return new_node; } // function to get count of non-leaf nodes int getLeafCount(Node* root){ // initializing queue for level order traversal queue<Node*> q; q.push(root); // initializing count variable int count = 0; while (!q.empty()){ Node* temp = q.front(); q.pop(); if (temp->left != NULL || temp->right != NULL) count++; if (temp->left) q.push(temp->left); if (temp->right) q.push(temp->right); } return count; } // driver code to test above function int main(){ struct Node* root = newNode(1); root->left = newNode(2); root->right = newNode(3); root->left->left = newNode(4); root->left->right = newNode(5); // function call cout << "Non-Leaf count of the tree is : " << getLeafCount(root) << endl; return 0; } // THIS CODE IS CONTRIBUTED BY KIRIT AGARWAL(KIRTIAGARWAL23121999) |
Java
// Java implementation to find non-leaf // count of a given Binary tree import java.util.LinkedList; import java.util.Queue; // class to represent the tree node class Node{ public int data; public Node left, right; public Node( int data){ data = data; left = right = null ; } } public class BinaryTree{ // utility function to get the new node static Node newNode( int data){ return new Node(data); } // function to get count of non-leaf nodes static int getLeafCount(Node root){ // initializing queue for level order traversal Queue<Node> q = new LinkedList<Node>(); q.add(root); int count = 0 ; while (!q.isEmpty()){ Node temp = q.poll(); if (temp.left != null || temp.right != null ){ count++; } if (temp.left != null ) q.add(temp.left); if (temp.right != null ) q.add(temp.right); } return count; } // driver code to test above function public static void main(String args[]){ Node root = newNode( 1 ); root.left = newNode( 2 ); root.right = newNode( 3 ); root.left.left = newNode( 4 ); root.left.right = newNode( 5 ); // function call System.out.println( "Non-leaf count of the tree is : " + getLeafCount(root)); } } |
Python3
# Python program to find non-leaf # count of a given binary tree # a binary tree node class Node: def __init__( self , data): self .data = data self .left = None self .right = None # utility function to get the new node def newNode(data): return Node(data) # function to get count of non-leaf nodes def getLeafCount(root): # initializing queue for level order traversal q = [] q.append(root) # initializing count variable count = 0 while ( len (q) > 0 ): temp = q.pop( 0 ) if (temp.left is not None or temp.right is not None ): count + = 1 if (temp.left is not None ): q.append(temp.left) if (temp.right is not None ): q.append(temp.right) return count # driver code to test above function root = newNode( 1 ) root.left = newNode( 2 ) root.right = newNode( 3 ) root.left.left = newNode( 4 ) root.left.right = newNode( 5 ) # function call print ( "Non-Leaf count of the tree is :" , end = " " ) print (getLeafCount(root)) |
C#
// C# implementation to find non-leaf // count of a given binary tree using System; using System.Collections.Generic; // class to represent tree node public class Node{ public int data; public Node left, right; public Node( int item){ data = item; left = null ; right = null ; } } public class BinaryTree { // utitliry function to get the new node static Node newNode( int data){ return new Node(data); } // function to get count of non-leaf nodes static int getLeafCount(Node root) { // intiializing queue for level order traversal Queue<Node> q = new Queue<Node>(); q.Enqueue(root); int count = 0; while (q.Count != 0){ Node temp = q.Dequeue(); if (temp.left != null || temp.right != null ) count++; if (temp.left != null ) q.Enqueue(temp.left); if (temp.right != null ) q.Enqueue(temp.right); } return count; } // driver program to test above function public static void Main(){ Node root = newNode(1); root.left = newNode(2); root.right = newNode(3); root.left.left = newNode(4); root.left.right = newNode(5); // function call Console.WriteLine( "Non-Leaf count of the tree is : " + getLeafCount(root)); } } |
Javascript
// JavaScript implementation to find non-leaf // count of a given binary tree // a binary tree node class Node{ constructor(data){ this .data = data; this .left = null ; this .right = null ; } } // utility function to get the new node function newNode(data){ return new Node(data); } // function to get the count of non-leaf nodes function getLeafCount(root) { // initializing queue for level order traversal let q = []; q.push(root); // initializing the count variable let count = 0; while (q.length > 0){ let temp = q.shift(); if (temp.left != null || temp.right != null ) count++; if (temp.left) q.push(temp.left); if (temp.right) q.push(temp.right); } return count; } // driver code to test above functions let root = newNode(1); root.left = newNode(2); root.right = newNode(3); root.left.left = newNode(4); root.left.right = newNode(5); // function call console.log( "Non-Leaf count of the tree is: " +getLeafCount(root)); // THIS CODE IS CONTRIBUTED BY YASH AGARWAL(YASHAGARWAL2852002) |
Non-Leaf count of the tree is : 2
Time Complexity: O(N) where N is the number of nodes in given binary tree.
Auxiliary Space: O(N) due to queue data structure.
Contact Us