Given a binary tree of N nodes. Count the frequency of an integer K in the binary tree.
Examples:
Input: N = 7, K = 2
1
/ \
2 3
/ \ / \
4 2 2 5
Output: 3
Explanation: 2 occurs 3 times in the tree.Input: N = 6, K = 5
1
/ \
4 5
/ \ / \
5 6 2 4
Output: 2
Explanation: 5 occurs 2 times in the tree.
Approach: The solution to the problem is based on the traversal of the given binary tree. Follow the steps as shown below:
- Perform inorder traversal of the given Binary Tree
- For each node in the tree, check whether it is equal to K or not
- If it is equal to K, increment the required count by 1.
- At the end, return the final count.
Below is the implementation of the above approach.
C++
// C++ code to implement the approach#include <bits/stdc++.h>using namespace std;// Structure of a tree nodestruct Node { int data; struct Node* left; struct Node* right; Node(int data) { this->data = data; left = right = NULL; }};// Function for inorder tree traversalint countOccurrence(struct Node* root, int K){ stack<Node*> s; Node* curr = root; // Variable for counting frequency of K int count = 0; while (curr != NULL || s.empty() == false) { // Reach the left most Node // of the curr Node while (curr != NULL) { // Place pointer to a tree node // on the stack before // traversing the node's // left subtree s.push(curr); curr = curr->left; } // Current must be NULL at this point curr = s.top(); s.pop(); // Increment count if element = K if (curr->data == K) count++; // Traverse the right subtree curr = curr->right; } return count;}// Driver codeint main(){ // Binary tree as shown in example struct Node* root = new Node(1); root->left = new Node(2); root->right = new Node(2); root->left->left = new Node(4); root->left->right = new Node(2); int K = 2; // Function call int ans = countOccurrence(root, K); cout << ans << endl; return 0;} |
Java
// JAVA code to implement the approachimport java.util.*;// Structure of a tree nodeclass Node { int data; Node left; Node right; Node(int data) { this.data = data; left = right = null; }}class GFG { // Function for inorder tree traversal public static int countOccurrence(Node root, int K) { Stack<Node> s = new Stack<Node>(); Node curr = root; // Variable for counting frequency of K int count = 0; while (curr != null || s.empty() == false) { // Reach the left most Node // of the curr Node while (curr != null) { // Place pointer to a tree node // on the stack before // traversing the node's // left subtree s.push(curr); curr = curr.left; } // Current must be NULL at this point curr = s.peek(); s.pop(); // Increment count if element = K if (curr.data == K) count++; // Traverse the right subtree curr = curr.right; } return count; } // Driver code public static void main(String[] args) { // Binary tree as shown in example Node root = new Node(1); root.left = new Node(2); root.right = new Node(2); root.left.left = new Node(4); root.left.right = new Node(2); int K = 2; // Function call int ans = countOccurrence(root, K); System.out.println(ans); }}// This code is contributed by Taranpreet |
Python3
# Python code for the above approach# Structure of a tree nodeclass Node: def __init__(self,d): self.data = d self.left = None self.right = None# Function for inorder tree traversaldef countOccurrence(root, K): s = [] curr = root # Variable for counting frequency of K count = 0 while (curr != None or len(s) != 0): # Reach the left most Node # of the curr Node while (curr != None): # Place pointer to a tree node # on the stack before # traversing the node's # left subtree s.append(curr) curr = curr.left # Current must be None at this point curr = s[len(s) - 1] s.pop() # Increment count if element = K if (curr.data == K): count += 1 # Traverse the right subtree curr = curr.right return count# Driver code# Binary tree as shown in exampleroot = Node(1)root.left = Node(2)root.right = Node(2)root.left.left = Node(4)root.left.right = Node(2)K = 2# Function callans = countOccurrence(root, K)print(ans) # This code is contributed by shinjanpatra |
C#
// C# code to implement the approachusing System;using System.Collections.Generic;// Structure of a tree nodepublic class Node { public int data; public Node left; public Node right; public Node(int data) { this.data = data; left = right = null; }}class GFG { // Function for inorder tree traversal public static int countOccurrence(Node root, int K) { Stack<Node> s = new Stack<Node> (); Node curr = root; // Variable for counting frequency of K int count = 0; while (curr != null || s.Count!=0) { // Reach the left most Node // of the curr Node while (curr != null) { // Place pointer to a tree node // on the stack before // traversing the node's // left subtree s.Push(curr); curr = curr.left; } // Current must be NULL at this point curr = s.Peek(); s.Pop(); // Increment count if element = K if (curr.data == K) count++; // Traverse the right subtree curr = curr.right; } return count; } // Driver Code public static void Main () { // Build a tree // Binary tree as shown in example Node root = new Node(1); root.left = new Node(2); root.right = new Node(2); root.left.left = new Node(4); root.left.right = new Node(2); int K = 2; // Function call int ans = countOccurrence(root, K); Console.WriteLine(ans); }}// This code is contributed by jana_sayantan. |
Javascript
<script> // JavaScript code for the above approach // Structure of a tree node class Node { constructor(d) { this.data = d; this.left = null; this.right = null; } }; // Function for inorder tree traversal function countOccurrence(root, K) { let s = []; let curr = root; // Variable for counting frequency of K let count = 0; while (curr != null || s.length != 0) { // Reach the left most Node // of the curr Node while (curr != null) { // Place pointer to a tree node // on the stack before // traversing the node's // left subtree s.push(curr); curr = curr.left; } // Current must be null at this point curr = s[s.length - 1]; s.pop(); // Increment count if element = K if (curr.data == K) count++; // Traverse the right subtree curr = curr.right; } return count; } // Driver code // Binary tree as shown in example let root = new Node(1); root.left = new Node(2); root.right = new Node(2); root.left.left = new Node(4); root.left.right = new Node(2); let K = 2; // Function call let ans = countOccurrence(root, K); document.write(ans + '<br>') // This code is contributed by Potta Lokesh </script> |
Output
3
Time Complexity: O(N)
Auxiliary Space: O(N)
Another Approach(using Recursion):
follow the below steps to solve the given problem recursively:
1) traverse the given binary tree in preorder fashion and keep track to count at each node
2) if the current node value is equal to given value(K) then increment k
3) recursively call for left and right subtree.
4) print count answer.
Below is the implementation of above approach:
C++
// c++ program to count frequency of k// in given binary tree#include<bits/stdc++.h>using namespace std;// Structure of a tree nodestruct Node { int data; struct Node* left; struct Node* right; Node(int data) { this->data = data; left = right = NULL; }};// Function for preorder tree traversal recursivelyvoid countOccurrence(Node* root, int K, int &count){ if(root == NULL) return; if(root->data == K) count++; countOccurrence(root->left, K, count); countOccurrence(root->right, K, count);}// Driver codeint main(){ // Binary tree as shown in example struct Node* root = new Node(1); root->left = new Node(2); root->right = new Node(2); root->left->left = new Node(4); root->left->right = new Node(2); int K = 2; int ans = 0; // Function call countOccurrence(root, K, ans); cout << ans << endl; return 0;}// this code is contributed by Yash Agarwal(yashagarwal2852002) |
Java
/*package whatever //do not write package name here */import java.io.*;// Java program to count frequency of k// in given binary tree// structure of a tree nodeclass Node { int data; Node left; Node right; Node(int data) { this.data = data; this.left = null; this.right = null; }}class GFG { static int count = 0; public static void countOccurrence(Node root, int k) { if (root == null) return; if (root.data == k) count++; countOccurrence(root.left, k); countOccurrence(root.right, k); } // function topreorder tree traversal recursively public static void main(String[] args) { Node root = new Node(1); root.left = new Node(2); root.right = new Node(2); root.left.left = new Node(4); root.left.right = new Node(2); int k = 2; int ans = 0; countOccurrence(root, k); System.out.println(count); }}// This code is contributed by anskalyan3. |
Python
# Python program to count frequency of k# in given binary tree# structure of tree nodeclass Node: def __init__(self,key): self.data = key self.left = None self.right = None # function to preorder tree traversal recursivelycount = 0def countOccurrence(root, K): if(root is None): return if(root.data == K): global count count = count + 1 countOccurrence(root.left, K) countOccurrence(root.right, K)# driver code# binary tree as shown in exampleroot = Node(1)root.left = Node(2)root.right = Node(2)root.left.left = Node(4)root.left.right = Node(2)K = 2# function callcountOccurrence(root, K)print(count) |
C#
// C# program to count frequency of k// in given binary treeusing System;using System.Collections.Generic;class Gfg{ static int count = 0; // Structure of a tree node class Node { public int data; public Node left; public Node right; public Node(int data) { this.data = data; left = right = null; } } // Function for preorder tree traversal recursively static void countOccurrence(Node root, int K) { if(root == null) return; if(root.data == K) count++; countOccurrence(root.left, K); countOccurrence(root.right, K); } // Driver code public static void Main(string[] args) { // Binary tree as shown in example Node root = new Node(1); root.left = new Node(2); root.right = new Node(2); root.left.left = new Node(4); root.left.right = new Node(2); int K = 2; // Function call countOccurrence(root, K); Console.Write(count); }}// This code is contributed by ratiagrawal. |
Javascript
// Javascript program to count frequency of k// in given binary tree// structure of a tree nodeclass Node{ constructor(data){ this.data = data; this.left = null; this.right = null; }}// function topreorder tree traversal recursivelylet count = 0;function countOccurrence(root, K){ if(root == null) return; if(root.data == K) count++; countOccurrence(root.left, K); countOccurrence(root.right, K);}// driver code// binary tree as shown in examplelet root = new Node(1);root.left = new Node(2);root.right = new Node(2);root.left.left = new Node(4);root.left.right = new Node(2);let K = 2;// function callcountOccurrence(root, K);console.log(count);// THIS CODE IS CONTRIBUTED BY KIRTI AGARWAL(KIRITAGARWAL23121999) |
Output
3
Time Complexity: O(N) where N is the number of nodes in given binary tree.
Auxiliary Space: O(h) where h is the height of the given tree due to recursion.
Another Iterative and Easiest Approach(Using Level Order Traversal with Queue):
Follow the below steps to solve the given problem:
- Perform level order traversal using Queue data structure.
- At each node in traversal check if it is equal to the given integer k then increment the count variable which is initialized by 0 in starting the level order traversal.
- Simply return the value of count variable.
Below is the implementation of above approach:
C++
// c++ program to count frequency of k// in given binary tree#include<bits/stdc++.h>using namespace std;// Structure of a tree nodestruct Node { int data; struct Node* left; struct Node* right; Node(int data) { this->data = data; left = right = NULL; }};// Function for preorder tree traversal recursivelyvoid countOccurrence(Node* root, int K, int &count){ // initialize queue for level order traversal queue<Node*> q; q.push(root); while(!q.empty()){ Node* front_node = q.front(); q.pop(); if(front_node->data == K) count++; if(front_node->left) q.push(front_node->left); if(front_node->right) q.push(front_node->right); }}// Driver codeint main(){ // Binary tree as shown in example struct Node* root = new Node(1); root->left = new Node(2); root->right = new Node(2); root->left->left = new Node(4); root->left->right = new Node(2); int K = 2; int ans = 0; // Function call countOccurrence(root, K, ans); cout << ans << endl; return 0;}// this code is contributed by Kirti Agarwal(kirtiagarwal23121999) |
Java
import java.util.LinkedList;import java.util.Queue;// Structure of a tree nodeclass Node { int data; Node left; Node right; Node(int data) { this.data = data; left = right = null; }}public class Main { // Function for preorder tree traversal recursively static void countOccurrence(Node root, int K, int[] count) { // Initialize queue for level order traversal Queue<Node> q = new LinkedList<Node>(); q.add(root); while (!q.isEmpty()) { Node front_node = q.poll(); if (front_node.data == K) { count[0]++; } if (front_node.left != null) { q.add(front_node.left); } if (front_node.right != null) { q.add(front_node.right); } } } // Driver code public static void main(String[] args) { // Binary tree as shown in example Node root = new Node(1); root.left = new Node(2); root.right = new Node(2); root.left.left = new Node(4); root.left.right = new Node(2); int K = 2; int[] ans = {0}; // Function call countOccurrence(root, K, ans); System.out.println(ans[0]); }}// This code is contributed by divyansh2212 |
Python3
# Python3 program to count frequency of k# in given binary tree# Structure of a tree nodeclass Node: def __init__(self, data): self.data = data self.left = None self.right = None# Function for preorder tree traversal recursivelydef countOccurrence(root, k): if root is None: return 0 count = 0 # initialize queue for level order traversal queue = [] queue.append(root) while(len(queue) > 0): node = queue.pop(0) if (node.data == k): count += 1 if node.left is not None: queue.append(node.left) if node.right is not None: queue.append(node.right) return count # Driver codeif __name__ == '__main__': # Binary tree as shown in example root = Node(1) root.left = Node(2) root.right = Node(2) root.left.left = Node(4) root.left.right = Node(2) k = 2 # Function Call print(countOccurrence(root, k)) |
C#
// C# program to count frequency of k// in given binary treeusing System;using System.Collections.Generic;// Structure of a tree nodepublic class Node { public int data; public Node left, right; public Node(int item) { data = item; left = right = null; }}public class BinaryTree { Node root; // Function for preorder tree traversal recursively public void CountOccurrence(int k, ref int count) { if (root == null) return; //initialize queue for level order traversal Queue<Node> queue = new Queue<Node>(); queue.Enqueue(root); while (queue.Count > 0) { Node frontNode = queue.Dequeue(); if (frontNode.data == k) count++; if (frontNode.left != null) queue.Enqueue(frontNode.left); if (frontNode.right != null) queue.Enqueue(frontNode.right); } } // Driver code public static void Main(string[] args) { // Binary tree as shown in example BinaryTree tree = new BinaryTree(); tree.root = new Node(1); tree.root.left = new Node(2); tree.root.right = new Node(2); tree.root.left.left = new Node(4); tree.root.left.right = new Node(2); int k = 2; int count = 0; // Function Call tree.CountOccurrence(k, ref count); Console.WriteLine(count); }} |
Javascript
// Structure of a tree nodeclass Node { constructor(data) { this.data = data; this.left = null; this.right = null; }}// Function for preorder tree traversal recursivelyfunction countOccurrence(root, K) { let count = 0; // initialize queue for level order traversal let q = []; q.push(root); while(q.length > 0){ let front_node = q.shift(); if(front_node.data == K) count++; if(front_node.left) q.push(front_node.left); if(front_node.right) q.push(front_node.right); } return count;}// Driver code// Binary tree as shown in examplelet root = new Node(1);root.left = new Node(2);root.right = new Node(2);root.left.left = new Node(4);root.left.right = new Node(2); let K = 2;let ans = countOccurrence(root, K);console.log(ans); |
Output
3
Time Complexity: O(N) where N is the number of nodes in given Binary tree because we simply traverse the each node only once.
Auxiliary space: O(N) due to queue data structure for storing the node level-wise.
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!
