Given a Binary tree, the task is to count the number of nodes with two children at a given level L.
Examples:
Input:
1
/ \
2 3
/ \ \
4 5 6
/ / \
7 8 9
L = 2
Output: 1
Input:
20
/ \
8 22
/ \ / \
5 3 4 25
/ \ / \ \
1 10 2 14 6
L = 3
Output: 2
Approach: Initialize a variable count = 0. Recursively traverse the tree in a level order manner. If the current level is same as the given level, then check whether the current node has two children. If it has two children then increment the variable count.
Below is the implementation of the above approach:
C++
// C++ program to find number of full nodes// at a given level#include <bits/stdc++.h>using namespace std;// A binary tree nodestruct Node { int data; struct Node *left, *right;};// Utility function to allocate memory for a new nodestruct Node* newNode(int data){ struct Node* node = new (struct Node); node->data = data; node->left = node->right = NULL; return (node);}// Function that returns the height of binary treeint height(struct Node* root){ if (root == NULL) return 0; int lheight = height(root->left); int rheight = height(root->right); return max(lheight, rheight) + 1;}// Level Order traversal to find the number of nodes// having two childrenvoid LevelOrder(struct Node* root, int level, int& count){ if (root == NULL) return; if (level == 1 && root->left && root->right) count++; else if (level > 1) { LevelOrder(root->left, level - 1, count); LevelOrder(root->right, level - 1, count); }}// Returns the number of full nodes// at a given levelint CountFullNodes(struct Node* root, int L){ // Stores height of tree int h = height(root); // Stores count of nodes at a given level // that have two children int count = 0; LevelOrder(root, L, count); return count;}// Driver codeint main(){ struct Node* root = newNode(7); root->left = newNode(5); root->right = newNode(6); root->left->left = newNode(8); root->left->right = newNode(1); root->left->left->left = newNode(2); root->left->left->right = newNode(11); root->right->left = newNode(3); root->right->right = newNode(9); root->right->right->right = newNode(13); root->right->right->left = newNode(10); root->right->right->right->left = newNode(4); root->right->right->right->right = newNode(12); int L = 3; cout << CountFullNodes(root, L); return 0;} |
Java
// Java program to find number of full nodes // at a given level class GFG{//INT classstatic class INT{ int a;}// A binary tree node static class Node { int data; Node left, right; }; // Utility function to allocate memory for a new node static Node newNode(int data) { Node node = new Node(); node.data = data; node.left = node.right = null; return (node); } // Function that returns the height of binary tree static int height(Node root) { if (root == null) return 0; int lheight = height(root.left); int rheight = height(root.right); return Math.max(lheight, rheight) + 1; } // Level Order traversal to find the number of nodes // having two children static void LevelOrder( Node root, int level, INT count) { if (root == null) return; if (level == 1 && root.left!=null && root.right!=null) count.a++; else if (level > 1) { LevelOrder(root.left, level - 1, count); LevelOrder(root.right, level - 1, count); } } // Returns the number of full nodes // at a given level static int CountFullNodes( Node root, int L) { // Stores height of tree int h = height(root); // Stores count of nodes at a given level // that have two children INT count =new INT(); count.a = 0; LevelOrder(root, L, count); return count.a; } // Driver code public static void main(String args[]){ Node root = newNode(7); root.left = newNode(5); root.right = newNode(6); root.left.left = newNode(8); root.left.right = newNode(1); root.left.left.left = newNode(2); root.left.left.right = newNode(11); root.right.left = newNode(3); root.right.right = newNode(9); root.right.right.right = newNode(13); root.right.right.left = newNode(10); root.right.right.right.left = newNode(4); root.right.right.right.right = newNode(12); int L = 3; System.out.print( CountFullNodes(root, L)); } }// This code is contributed by Arnab Kundu |
Python3
# Python3 program to find number of # full nodes at a given level# INT classclass INT: def __init__(self): self.a = 0# A binary tree nodeclass Node: def __init__(self, data): self.left = None self.right = None self.data = data # Utility function to allocate # memory for a new nodedef newNode(data): node = Node(data) return node# Function that returns the# height of binary treedef height(root): if (root == None): return 0; lheight = height(root.left); rheight = height(root.right); return max(lheight, rheight) + 1;# Level Order traversal to find the# number of nodes having two childrendef LevelOrder(root, level, count): if (root == None): return; if (level == 1 and root.left != None and root.right != None): count.a += 1 elif (level > 1): LevelOrder(root.left, level - 1, count); LevelOrder(root.right, level - 1, count); # Returns the number of full nodes# at a given leveldef CountFullNodes(root, L): # Stores height of tree h = height(root); # Stores count of nodes at a # given level that have two children count = INT() LevelOrder(root, L, count); return count.a# Driver code if __name__=="__main__": root = newNode(7); root.left = newNode(5); root.right = newNode(6); root.left.left = newNode(8); root.left.right = newNode(1); root.left.left.left = newNode(2); root.left.left.right = newNode(11); root.right.left = newNode(3); root.right.right = newNode(9); root.right.right.right = newNode(13); root.right.right.left = newNode(10); root.right.right.right.left = newNode(4); root.right.right.right.right = newNode(12); L = 3; print(CountFullNodes(root, L)) # This code is contributed by rutvik_56 |
C#
// C# program to find number of full nodes // at a given levelusing System;class GFG { // INT class public class INT { public int a; } // A binary tree node public class Node { public int data; public Node left, right; }; // Utility function to allocate memory for a new node static Node newNode(int data) { Node node = new Node(); node.data = data; node.left = node.right = null; return (node); } // Function that returns the height of binary tree static int height(Node root) { if (root == null) return 0; int lheight = height(root.left); int rheight = height(root.right); return Math.Max(lheight, rheight) + 1; } // Level Order traversal to find the number of nodes // having two children static void LevelOrder( Node root, int level, INT count) { if (root == null) return; if (level == 1 && root.left!=null && root.right!=null) count.a++; else if (level > 1) { LevelOrder(root.left, level - 1, count); LevelOrder(root.right, level - 1, count); } } // Returns the number of full nodes // at a given level static int CountFullNodes( Node root, int L) { // Stores height of tree int h = height(root); // Stores count of nodes at a given level // that have two children INT count =new INT(); count.a = 0; LevelOrder(root, L, count); return count.a; } // Driver code public static void Main(String []args) { Node root = newNode(7); root.left = newNode(5); root.right = newNode(6); root.left.left = newNode(8); root.left.right = newNode(1); root.left.left.left = newNode(2); root.left.left.right = newNode(11); root.right.left = newNode(3); root.right.right = newNode(9); root.right.right.right = newNode(13); root.right.right.left = newNode(10); root.right.right.right.left = newNode(4); root.right.right.right.right = newNode(12); int L = 3; Console.Write( CountFullNodes(root, L)); } } // This code is contributed by 29AjayKumar |
Javascript
<script>// Javascript program to find number// of full nodes at a given level// INT classlet a = 0;// A binary tree nodeclass Node{ constructor(data) { this.left = null; this.right = null; this.data = data; }}// Utility function to allocate memory// for a new nodefunction newNode(data){ let node = new Node(data); return (node);}// Function that returns the height// of binary treefunction height(root){ if (root == null) return 0; let lheight = height(root.left); let rheight = height(root.right); return Math.max(lheight, rheight) + 1;}// Level Order traversal to find the number // of nodes having two childrenfunction LevelOrder(root, level){ if (root == null) return; if (level == 1 && root.left != null && root.right != null) a++; else if (level > 1) { LevelOrder(root.left, level - 1); LevelOrder(root.right, level - 1); }}// Returns the number of full nodes// at a given levelfunction CountFullNodes(root, L){ // Stores height of tree let h = height(root); LevelOrder(root, L); return a;}// Driver codelet root = newNode(7);root.left = newNode(5);root.right = newNode(6);root.left.left = newNode(8);root.left.right = newNode(1);root.left.left.left = newNode(2);root.left.left.right = newNode(11);root.right.left = newNode(3);root.right.right = newNode(9);root.right.right.right = newNode(13);root.right.right.left = newNode(10);root.right.right.right.left = newNode(4);root.right.right.right.right = newNode(12);let L = 3;document.write(CountFullNodes(root, L));// This code is contributed by mukesh07</script> |
Output:
2
Time Complexity: O(N)
Auxiliary Space: O(N)
Another Approach:
We can solve this problem by level order traversal using queue. In which we find the element which have two children at given level and increment the count variable.
Below is the implementation of above approach:
C++
// C++ program to find number of full nodes// at a given level#include <bits/stdc++.h>using namespace std;// A binary tree nodestruct Node { int data; struct Node* left; struct Node* right;};// function to allocate memory for a new nodestruct Node* newNode(int data){ struct Node* node = new Node(); node->data = data; node->left = node->right = NULL; return node;}// function to return the number// of nodesint levelOrderTraversal(Node* root, int L){ int count = 0; int level = 0; queue<Node*> q; q.push(root); while (!q.empty()) { level++; int n = q.size(); for (int i = 0; i < n; i++) { Node* front_node = q.front(); q.pop(); if (L == level && front_node->left != NULL && front_node->right != NULL) { count++; } if (front_node->left != NULL) q.push(front_node->left); if (front_node->right != NULL) q.push(front_node->right); } } return count;}// Driver Codeint main(){ Node* root = newNode(7); root->left = newNode(5); root->right = newNode(6); root->left->left = newNode(8); root->left->right = newNode(1); root->left->left->left = newNode(2); root->left->left->right = newNode(11); root->right->left = newNode(3); root->right->right = newNode(9); root->right->right->right = newNode(13); root->right->right->left = newNode(10); root->right->right->right->left = newNode(4); root->right->right->right->right = newNode(12); int L = 3; cout << levelOrderTraversal(root, L) << endl; return 0;}// This code is contributed by Kirti Agarwal |
Java
// Java program to find number of full nodes// at a given levelimport java.util.LinkedList;import java.util.Queue;// A binary tree nodeclass Node { int data; Node left; Node right; // constructor to initialize data and left and right pointers Node(int data) { this.data = data; this.left = null; this.right = null; }}public class Main { // function to return the number of full nodes static int levelOrderTraversal(Node root, int L) { int count = 0; int level = 0; Queue<Node> q = new LinkedList<Node>(); q.add(root); while (!q.isEmpty()) { level++; int n = q.size(); for (int i = 0; i < n; i++) { Node front_node = q.poll(); if (L == level && front_node.left != null && front_node.right != null) { count++; } if (front_node.left != null) q.add(front_node.left); if (front_node.right != null) q.add(front_node.right); } } return count; } // Driver Code public static void main(String[] args) { Node root = new Node(7); root.left = new Node(5); root.right = new Node(6); root.left.left = new Node(8); root.left.right = new Node(1); root.left.left.left = new Node(2); root.left.left.right = new Node(11); root.right.left = new Node(3); root.right.right = new Node(9); root.right.right.right = new Node(13); root.right.right.left = new Node(10); root.right.right.right.left = new Node(4); root.right.right.right.right = new Node(12); int L = 3; System.out.println(levelOrderTraversal(root, L)); }} |
Python
# Python3 program to find number of# full nodes at a given level# a binary tree nodeclass Node: def __init__(self, data): self.data = data self.left = None self.right = None # function to allocate memory for a new nodedef newNode(data): return Node(data)# function to return the number# of nodesdef levelOrderTraversal(root, L): count = 0 level = 0 q = [] q.append(root) while(len(q) > 0): level += 1 n = len(q) for i in range(n): front_node = q.pop(0) if(L == level and front_node.left is not None and front_node.right is not None): count += 1 if(front_node.left is not None): q.append(front_node.left) if(front_node.right is not None): q.append(front_node.right) return count;#driver code to test above functionsroot = newNode(7);root.left = newNode(5);root.right = newNode(6);root.left.left = newNode(8);root.left.right = newNode(1);root.left.left.left = newNode(2);root.left.left.right = newNode(11);root.right.left = newNode(3);root.right.right = newNode(9);root.right.right.right = newNode(13);root.right.right.left = newNode(10);root.right.right.right.left = newNode(4);root.right.right.right.right = newNode(12);L = 3;print(levelOrderTraversal(root, L)) |
Javascript
// JavaScript program to find number of full nodes// at a given level// a binary tree nodeclass Node{ constructor(data){ this.data = data; this.left = this.right = null; }}// function to allcated memory for a new nodefunction newNode(data){ return new Node(data);}// function to return the number// of nodesfunction levelOrderTraversal(root, L){ let count = 0; let level = 0; let q = []; q.push(root); while(q.length > 0){ level++; let n = q.length; for(let i = 0; i<n; i++){ let front_node = q.shift(); if(L == level && front_node.left != null && front_node.right != null){ count++; } if(front_node.left) q.push(front_node.left); if(front_node.right) q.push(front_node.right); } } return count;}// driver codelet root = newNode(7);root.left = newNode(5);root.right = newNode(6);root.left.left = newNode(8);root.left.right = newNode(1);root.left.left.left = newNode(2);root.left.left.right = newNode(11);root.right.left = newNode(3);root.right.right = newNode(9);root.right.right.right = newNode(13);root.right.right.left = newNode(10);root.right.right.right.left = newNode(4);root.right.right.right.right = newNode(12);let L = 3;console.log(levelOrderTraversal(root, L));// THIS CODE IS CONTRIBUTED BY YASH AGARWAL(YASHAGARWAL2852002) |
C#
using System;using System.Collections.Generic;// C# program to find number of full nodes// at a given levelpublic class Node { public int data; public Node left, right; public Node(int data) { this.data = data; this.left = this.right = null; }}public class BinaryTree { public static int LevelOrderTraversal(Node root, int L) { int count = 0, level = 0; Queue<Node> q = new Queue<Node>(); q.Enqueue(root); while (q.Count > 0) { level++; int n = q.Count; for (int i = 0; i < n; i++) { Node front_node = q.Dequeue(); if (L == level && front_node.left != null && front_node.right != null) { count++; } if (front_node.left != null) q.Enqueue(front_node.left); if (front_node.right != null) q.Enqueue(front_node.right); } } return count; } public static void Main() { Node root = new Node(7); root.left = new Node(5); root.right = new Node(6); root.left.left = new Node(8); root.left.right = new Node(1); root.left.left.left = new Node(2); root.left.left.right = new Node(11); root.right.left = new Node(3); root.right.right = new Node(9); root.right.right.right = new Node(13); root.right.right.left = new Node(10); root.right.right.right.left = new Node(4); root.right.right.right.right = new Node(12); int L = 3; Console.WriteLine(LevelOrderTraversal(root, L)); }} |
Output
2
Time Complexity: O(N)
Auxiliary Space: O(N)
Feeling lost in the world of random DSA topics, wasting time without progress? It’s time for a change! Join our DSA course, where we’ll guide you on an exciting journey to master DSA efficiently and on schedule.
Ready to dive in? Explore our Free Demo Content and join our DSA course, trusted by over 100,000 neveropen!
Ready to dive in? Explore our Free Demo Content and join our DSA course, trusted by over 100,000 neveropen!
