Given a value K and a binary tree, the task is to find out the number of subtrees having bitwise OR of all its elements equal to K.
Examples:
Input: K = 5, Tree = 2 / \ 1 1 / \ \ 10 5 4 Output: 2 Explanation: Subtree 1: 5 It has only one element i.e. 5. So bitwise OR of subtree = 5 Subtree 2: 1 \ 4 it has 2 elements and bitwise OR of them is also 5 Input: K = 3, Tree = 4 / \ 3 9 / \ 2 2 Output: 1
Approach:
- Traverse the tree recursively using pre-order traversal.
- For each node keep calculating the bitwise OR of its subtree as:
bitwise OR of its subtree = (bitwise OR of node’s left subtree) | (bitwise OR of node’s right subtree) | (node’s value)
- If the bitwise OR of any subtree is K, increment the counter variable.
- Print the value in the counter as the required count.
C++
// C++ program to find the count of // subtrees in a Binary Tree // having bitwise OR value K #include <bits/stdc++.h> using namespace std; // A binary tree node struct Node { int data; struct Node *left, *right; }; // A utility function to // allocate a new node struct Node* newNode( int data) { struct Node* newNode = new Node; newNode->data = data; newNode->left = newNode->right = NULL; return (newNode); } // Recursive Function to compute the count int rec(Node* root, int & res, int & k) { // Base Case: // If node is NULL, return 0 if (root == NULL) { return 0; } // Calculating the bitwise OR // of the current subtree int orr = root->data; orr |= rec(root->left, res, k); orr |= rec(root->right, res, k); // Increment res // if xr is equal to k if (orr == k) { res++; } // Return the bitwise OR value // of the current subtree return orr; } // Function to find the required count int FindCount(Node* root, int K) { // Initialize result variable 'res' int res = 0; // Recursively traverse the tree // and compute the count rec(root, res, K); // return the count 'res' return res; } // Driver program int main( void ) { /* 2 / \ 1 1 / \ \ 10 5 4 */ // Create the binary tree // by adding nodes to it struct Node* root = newNode(2); root->left = newNode(1); root->right = newNode(1); root->right->right = newNode(4); root->left->left = newNode(10); root->left->right = newNode(5); int K = 5; cout << FindCount(root, K); return 0; } |
Java
// Java program to find the count of // subtrees in a Binary Tree // having bitwise OR value K import java.io.*; class GFG { // A binary tree node static class Node { public int data; public Node left, right; }; static int res; static int k; // A utility function to // allocate a new node static Node newNode( int data) { Node newNode = new Node(); newNode.data = data; newNode.left = null ; newNode.right = null ; return newNode; } static int rec(Node root) { // Base Case: // If node is null, return 0 if (root == null ) { return 0 ; } // Calculating the XOR // of the current subtree int xr = (root.data); xr |= rec(root.left); xr |= rec(root.right); // Increment res // if xr is equal to k if (xr == k) { res++; } // Return the XOR value // of the current subtree return xr; } // Function to find the required count static int findCount(Node root, int K) { // Initialize result variable 'res' res = 0 ; k = K; // Recursively traverse the tree // and compute the count rec(root); // Return the count 'res' return res; } // Driver code public static void main (String[] args) { /* 2 / \ 1 1 / \ \ 10 5 4 */ // Create the binary tree // by adding nodes to it Node root = newNode( 2 ); root.left = newNode( 1 ); root.right = newNode( 1 ); root.right.right = newNode( 4 ); root.left.left =newNode( 10 ); root.left.right = newNode( 5 ); int K = 5 ; System.out.println(findCount(root, K)); } } // This code is contributed by avanitrachhadiya2155 |
Python3
# Python3 program to find the count of # subtrees in a Binary Tree # having bitwise OR value K # A binary tree node class Node: def __init__( self , data): self .data = data self .left = None self .right = None # A utility function to # allocate a new node def newNode(data): temp = Node(data) return temp # Recursive Function to compute the count def rec(root, res, k): # Base Case: # If node is NULL, return 0 if (root = = None ): return [ 0 , res]; # Calculating the bitwise OR # of the current subtree orr = root.data; tmp, res = rec(root.left, res, k); orr | = tmp tmp, res = rec(root.right, res, k); orr | = tmp # Increment res # if xr is equal to k if (orr = = k): res + = 1 # Return the bitwise OR value # of the current subtree return orr, res; # Function to find the required count def FindCount(root, K): # Initialize result variable 'res' res = 0 ; # Recursively traverse the tree # and compute the count tmp,res = rec(root, res, K); # return the count 'res' return res; # Driver program if __name__ = = '__main__' : ''' 2 / \ 1 1 / \ \ 10 5 4 ''' # Create the binary tree # by adding nodes to it root = newNode( 2 ); root.left = newNode( 1 ); root.right = newNode( 1 ); root.right.right = newNode( 4 ); root.left.left = newNode( 10 ); root.left.right = newNode( 5 ); K = 5 ; print (FindCount(root, K)) # This code is contributed by rutvik_56 |
C#
// C# program to find the count of // subtrees in a Binary Tree // having bitwise OR value K using System; class GFG{ // A binary tree node class Node { public int data; public Node left, right; }; static int res; static int k; // A utility function to // allocate a new node static Node newNode( int data) { Node newNode = new Node(); newNode.data = data; newNode.left= null ; newNode.right = null ; return newNode; } static int rec(Node root) { // Base Case: // If node is null, return 0 if (root == null ) { return 0; } // Calculating the XOR // of the current subtree int xr = (root.data); xr |= rec(root.left); xr |= rec(root.right); // Increment res // if xr is equal to k if (xr == k) { res++; } // Return the XOR value // of the current subtree return xr; } // Function to find the required count static int findCount(Node root, int K) { // Initialize result variable 'res' res = 0; k = K; // Recursively traverse the tree // and compute the count rec(root); // Return the count 'res' return res; } // Driver code public static void Main(String []args) { /* 2 / \ 1 1 / \ \ 10 5 4 */ // Create the binary tree // by adding nodes to it Node root = newNode(2); root.left = newNode(1); root.right = newNode(1); root.right.right = newNode(4); root.left.left =newNode(10); root.left.right = newNode(5); int K = 5; Console.WriteLine(findCount(root, K)); } } // This code is contributed by mohit kumar |
Javascript
<script> // Javascript program to find the count of // subtrees in a Binary Tree having bitwise // OR value K // Structure of node class Node { // Utility function to // create a new node constructor(key) { this .data = key; this .left = this .right = null ; } } let res, k; function rec(root) { // Base Case: // If node is null, return 0 if (root == null ) { return 0; } // Calculating the XOR // of the current subtree let xr = (root.data); xr |= rec(root.left); xr |= rec(root.right); // Increment res // if xr is equal to k if (xr == k) { res++; } // Return the XOR value // of the current subtree return xr; } // Function to find the required count function findCount(root, K) { // Initialize result variable 'res' res = 0; k = K; // Recursively traverse the tree // and compute the count rec(root); // Return the count 'res' return res; } // Driver code /* 2 / \ 1 1 / \ \ 10 5 4 */ // Create the binary tree // by adding nodes to it let root = new Node(2); root.left = new Node(1); root.right = new Node(1); root.right.right = new Node(4); root.left.left = new Node(10); root.left.right = new Node(5); let K = 5; document.write(findCount(root, K)); // This code is contributed by patel2127 </script> |
2
Time Complexity: As in the above approach, we are iterating over each node only once, therefore it will take O(N) time where N is the number of nodes in the Binary tree.
Auxiliary Space Complexity: As in the above approach there is no extra space used, therefore the Auxiliary Space complexity will be O(1).