Count frequency of K in given Binary Tree

0 0 11 minutes read

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 node
struct Node {
    int data;
    struct Node* left;
    struct Node* right;
    Node(int data)
    {
        this->data = data;
        left = right = NULL;
    }
};
 
// Function for inorder tree traversal
int 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 code
int 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 approach
import java.util.*;
 
// Structure of a tree node
class 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 node
class Node:
    def __init__(self,d):
        self.data = d
        self.left = None
        self.right = None
 
# Function for inorder tree traversal
def 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 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
ans = countOccurrence(root, K)
print(ans)
 
 # This code is contributed by shinjanpatra

C#

// C# code to implement the approach
using System;
using System.Collections.Generic;
 
// Structure of a tree node
public  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

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 node
struct Node {
    int data;
    struct Node* left;
    struct Node* right;
    Node(int data)
    {
        this->data = data;
        left = right = NULL;
    }
};
 
// Function for preorder tree traversal recursively
void 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 code
int 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 node
class 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 node
class Node:
    def __init__(self,key):
        self.data = key
        self.left = None
        self.right = None
     
 
# function to preorder tree traversal recursively
count = 0
def 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 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
countOccurrence(root, K)
print(count)

C#

// C# program to count frequency of k
// in given binary tree
using 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 node
class Node{
    constructor(data){
        this.data = data;
        this.left = null;
        this.right = null;
    }
}
 
// function topreorder tree traversal recursively
let 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 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
countOccurrence(root, K);
console.log(count);
// THIS CODE IS CONTRIBUTED BY KIRTI AGARWAL(KIRITAGARWAL23121999)

Output

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 node
struct Node {
    int data;
    struct Node* left;
    struct Node* right;
    Node(int data)
    {
        this->data = data;
        left = right = NULL;
    }
};
 
// Function for preorder tree traversal recursively
void 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 code
int 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 node
class 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 node
class Node:
    def __init__(self, data):
        self.data = data
        self.left = None
        self.right = None
 
# Function for preorder tree traversal recursively
def 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 code
if __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 tree
 
using System;
using System.Collections.Generic;
 
// Structure of a tree node
public 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 node
class Node {
    constructor(data) {
        this.data = data;
        this.left = null;
        this.right = null;
    }
}
 
// Function for preorder tree traversal recursively
function 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 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;
let ans = countOccurrence(root, K);
console.log(ans);

Output

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.

Recommended

Solve DSA problems on GfG Practice.

Solve Problems

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 zambiatek!