Queries to calculate Bitwise OR of each subtree of a given node in an N-ary Tree

19 June 2025

2

Given an N-ary Tree consisting of N nodes valued from 1 to N, an array arr[] consisting of N positive integers, where arr[i] is the value associated with the i^th node, and Q queries, each consisting of a node. The task for each query is to find the Bitwise OR of node values present in the subtree of the given node.

Examples:

Input: arr[] = {2, 3, 4, 8, 16} Queries[]: {2, 3, 1}

Output: 3 28 31
Explanation:
Query 1: Bitwise OR(subtree(Node 2)) = Bitwise OR(Node 2) = Bitwise OR(3) = 3
Query 2: Bitwise OR(subtree(Node 3)) = Bitwise OR(Node 3, Node 4, Node 5) = Bitwise OR(4, 8, 16) = 28
Query 3: Bitwise OR(subtree(Node 1)) = Bitwise OR(Node1, Node 2, Node 3, Node 4, Node 5) = Bitwise OR(2, 3, 4, 8, 16) = 31

Input: arr[] = {2, 3, 4, 8, 16} Queries[]: {4, 5}

Output: 8 16
Explanation:
Query 1: Bitwise OR(subtree(Node 4)) = bitwise OR(Node 4) = 8
Query 2: Bitwise OR(subtree(Node 5)) = bitwise OR(Node 5) = 16

Naive Approach: The simplest approach to solve this problem is to traverse the subtree of the given node and for each query, calculate the Bitwise OR of every node in the subtree of that node and print that value.
Time Complexity: O(Q * N)
Auxiliary Space: O(Q * N)

Efficient Approach: To optimize the above approach, the idea is to precompute the Bitwise OR of all subtrees present in the given tree, and for each query, find the Bitwise XOR of subtrees for every given node. Follow the steps below to solve the problem:

Initialize a vector ans[] to store the Bitwise OR of all subtrees present in the given Tree.
Precompute the Bitwise OR for every subtree using Depth First Search(DFS).
If the node is a leaf node, the bitwise OR of this node is the node value itself.
Otherwise, the Bitwise OR for the subtree is equal to the Bitwise OR of all subtree values of its children.
After completing the above steps, print the value stored at ans[Queries[i]] for every i^th query.

Below is the implementation of the above approach:

C++

// C++ program for the above approach
 
#include <bits/stdc++.h>
using namespace std;
 
// Maximum Number of nodes
const int N = 1e5 + 5;
 
// Adjacency list
vector<int> adj[N];
 
// Stores Bitwise OR of each node
vector<int> answer(N);
 
// Function to add edges to the Tree
void addEdgesToGraph(int Edges[][2],
                     int N)
{
    // Traverse the edges
    for (int i = 0; i < N - 1; i++) {
        int u = Edges[i][0];
        int v = Edges[i][1];
 
        // Add edges
        adj[u].push_back(v);
        adj[v].push_back(u);
    }
}
 
// Function to perform DFS
// Traversal on the given tree
void DFS(int node, int parent, int Val[])
{
    // Initialize answer with bitwise
    // OR of current node
    answer[node] = Val[node];
 
    // Iterate over each child
    // of the current node
    for (int child : adj[node]) {
 
        // Skip parent node
        if (child == parent)
            continue;
 
        // Call DFS for each child
        DFS(child, node, Val);
 
        // Taking bitwise OR of the
        // answer of the child to
        // find node's OR value
        answer[node] = (answer[node]
                        | answer[child]);
    }
}
 
// Function to call DFS from the'=
// root for precomputing answers
void preprocess(int Val[])
{
    DFS(1, -1, Val);
}
 
// Function to calculate and print
// the Bitwise OR for Q queries
void findSubtreeOR(int Queries[], int Q,
                   int Val[])
{
    // Perform preprocessing
    preprocess(Val);
 
    // Iterate over each given query
    for (int i = 0; i < Q; i++) {
 
        cout << answer[Queries[i]]
             << ' ';
    }
}
 
// Utility function to find and
// print bitwise OR for Q queries
void findSubtreeORUtil(
    int N, int Edges[][2], int Val[],
    int Queries[], int Q)
{
    // Function to add edges to graph
    addEdgesToGraph(Edges, N);
 
    // Function call
    findSubtreeOR(Queries, Q, Val);
}
 
// Driver Code
int main()
{
    // Number of nodes
    int N = 5;
    int Edges[][2]
        = { { 1, 2 }, { 1, 3 }, 
            { 3, 4 }, { 3, 5 } };
 
    int Val[] = { 0, 2, 3, 4, 8, 16 };
    int Queries[] = { 2, 3, 1 };
 
    int Q = sizeof(Queries)
            / sizeof(Queries[0]);
 
    // Function call
    findSubtreeORUtil(N, Edges, Val,
                      Queries, Q);
 
    return 0;
}

Java

// Java program for above approach
import java.util.*;
import java.lang.*;
import java.io.*;
 
class GFG
{
 
  // Maximum Number of nodes
  static int N = (int)1e5 + 5;
 
  // Adjacency list
  static ArrayList<ArrayList<Integer>> adj;
 
  // Stores Bitwise OR of each node
  static int[] answer;
 
  // Function to add edges to the Tree
  static void addEdgesToGraph(int Edges[][],
                              int N)
  {
    // Traverse the edges
    for (int i = 0; i < N - 1; i++) 
    {
      int u = Edges[i][0];
      int v = Edges[i][1];
 
      // Add edges
      adj.get(u).add(v);
      adj.get(v).add(u);
    }
  }
 
  // Function to perform DFS
  // Traversal on the given tree
  static void DFS(int node, int parent, int Val[])
  {
 
    // Initialize answer with bitwise
    // OR of current node
    answer[node] = Val[node];
 
    // Iterate over each child
    // of the current node
    for (Integer child : adj.get(node))
    {
 
      // Skip parent node
      if (child == parent)
        continue;
 
      // Call DFS for each child
      DFS(child, node, Val);
 
      // Taking bitwise OR of the
      // answer of the child to
      // find node's OR value
      answer[node] = (answer[node]
                      | answer[child]);
    }
  }
 
  // Function to call DFS from the'=
  // root for precomputing answers
  static void preprocess(int Val[])
  {
    DFS(1, -1, Val);
  }
 
  // Function to calculate and print
  // the Bitwise OR for Q queries
  static void findSubtreeOR(int Queries[], int Q,
                            int Val[])
  {
     
    // Perform preprocessing
    preprocess(Val);
 
    // Iterate over each given query
    for (int i = 0; i < Q; i++) 
    {
      System.out.println(answer[Queries[i]] + " ");
    }
  }
 
  // Utility function to find and
  // print bitwise OR for Q queries
  static void findSubtreeORUtil(int N, int Edges[][], 
                                int Val[], int Queries[], 
                                int Q)
  {
 
    // Function to add edges to graph
    addEdgesToGraph(Edges, N);
 
    // Function call
    findSubtreeOR(Queries, Q, Val);
  }
 
  // Driver function
  public static void main (String[] args)
  {
 
    adj = new ArrayList<>();
    for(int i = 0; i < N; i++)
      adj.add(new ArrayList<>());
    answer = new int[N];
    N = 5;
    int Edges[][] = { { 1, 2 }, { 1, 3 },
                     { 3, 4 }, { 3, 5 } };
 
    int Val[] = { 0, 2, 3, 4, 8, 16 };
    int Queries[] = { 2, 3, 1 };
    int Q = Queries.length;
 
    // Function call
    findSubtreeORUtil(N, Edges, Val,
                      Queries, Q);
  }
}
 
// This code is contributed by offbeat

Python3

# Python3 program for the above approach
  
# Maximum Number of nodes
N = 100005;
  
# Adjacency list
adj = [[] for i in range(N)];
  
# Stores Bitwise OR of each node
answer = [0 for i in range(N)]
  
# Function to add edges to the Tree
def addEdgesToGraph(Edges, N):
 
    # Traverse the edges
    for i in range(N - 1):
     
        u = Edges[i][0];
        v = Edges[i][1];
  
        # Add edges
        adj[u].append(v);
        adj[v].append(u);
     
# Function to perform DFS
# Traversal on the given tree
def DFS(node, parent, Val):
 
    # Initialize answer with bitwise
    # OR of current node
    answer[node] = Val[node];
  
    # Iterate over each child
    # of the current node
    for child in adj[node]:
     
        # Skip parent node
        if (child == parent):
            continue;
  
        # Call DFS for each child
        DFS(child, node, Val);
  
        # Taking bitwise OR of the
        # answer of the child to
        # find node's OR value
        answer[node] = (answer[node]
                        | answer[child]);
     
# Function to call DFS from the'=
# root for precomputing answers
def preprocess( Val):
 
    DFS(1, -1, Val);
 
# Function to calculate and print
# the Bitwise OR for Q queries
def findSubtreeOR(Queries, Q, Val):
 
    # Perform preprocessing
    preprocess(Val);
  
    # Iterate over each given query
    for i in range(Q):
         
        print(answer[Queries[i]], end=' ')
   
# Utility function to find and
# print bitwise OR for Q queries
def findSubtreeORUtil( N, Edges, Val, Queries, Q):
 
    # Function to add edges to graph
    addEdgesToGraph(Edges, N);
  
    # Function call
    findSubtreeOR(Queries, Q, Val);
  
# Driver Code
if __name__=='__main__':
     
    # Number of nodes
    N = 5;
    Edges = [ [ 1, 2 ], [ 1, 3 ], [ 3, 4 ], [ 3, 5 ] ];
  
    Val = [ 0, 2, 3, 4, 8, 16 ];
    Queries = [ 2, 3, 1 ];
  
    Q = len(Queries)
  
    # Function call
    findSubtreeORUtil(N, Edges, Val,Queries, Q);
 
    # This code is contributed by rutvik_56

C#

// C# program to generate
// n-bit Gray codes
using System;
using System.Collections.Generic;
class GFG 
{
 
  // Maximum Number of nodes
  static int N = (int)1e5 + 5;
 
  // Adjacency list
  static List<List<int> > adj;
 
  // Stores Bitwise OR of each node
  static int[] answer;
 
  // Function to Add edges to the Tree
  static void AddEdgesToGraph(int[, ] Edges, int N)
  {
 
    // Traverse the edges
    for (int i = 0; i < N - 1; i++) {
      int u = Edges[i, 0];
      int v = Edges[i, 1];
 
      // Add edges
      adj[u].Add(v);
      adj[v].Add(u);
    }
  }
 
  // Function to perform DFS
  // Traversal on the given tree
  static void DFS(int node, int parent, int[] Val)
  {
 
    // Initialize answer with bitwise
    // OR of current node
    answer[node] = Val[node];
 
    // Iterate over each child
    // of the current node
    foreach(int child in adj[node])
    {
 
      // Skip parent node
      if (child == parent)
        continue;
 
      // Call DFS for each child
      DFS(child, node, Val);
 
      // Taking bitwise OR of the
      // answer of the child to
      // find node's OR value
      answer[node] = (answer[node] | answer[child]);
    }
  }
 
  // Function to call DFS from the'=
  // root for precomputing answers
  static void preprocess(int[] Val) { DFS(1, -1, Val); }
 
  // Function to calculate and print
  // the Bitwise OR for Q queries
  static void findSubtreeOR(int[] Queries, int Q,
                            int[] Val)
  {
 
    // Perform preprocessing
    preprocess(Val);
 
    // Iterate over each given query
    for (int i = 0; i < Q; i++) {
      Console.Write(answer[Queries[i]] + " ");
    }
  }
 
  // Utility function to find and
  // print bitwise OR for Q queries
  static void findSubtreeORUtil(int N, int[, ] Edges,
                                int[] Val, int[] Queries,
                                int Q)
  {
 
    // Function to Add edges to graph
    AddEdgesToGraph(Edges, N);
 
    // Function call
    findSubtreeOR(Queries, Q, Val);
  }
 
  // Driver function
  public static void Main(String[] args)
  {
 
    adj = new List<List<int> >();
    for (int i = 0; i < N; i++)
      adj.Add(new List<int>());
    answer = new int[N];
    N = 5;
    int[, ] Edges
      = { { 1, 2 }, { 1, 3 }, { 3, 4 }, { 3, 5 } };
 
    int[] Val = { 0, 2, 3, 4, 8, 16 };
    int[] Queries = { 2, 3, 1 };
    int Q = Queries.Length;
 
    // Function call
    findSubtreeORUtil(N, Edges, Val, Queries, Q);
  }
}
 
// This code is contributed by grand_master.

Javascript

<script>
// Javascript program for the above approach
 
// Maximum Number of nodes
const N = 1e5 + 5;
 
// Adjacency list
let adj = [];
 
for (let i = 0; i < N; i++) {
    adj.push([])
}
 
// Stores Bitwise OR of each node
let answer = new Array(N);
 
// Function to add edges to the Tree
function addEdgesToGraph(Edges, N) {
    // Traverse the edges
    for (let i = 0; i < N - 1; i++) {
        let u = Edges[i][0];
        let v = Edges[i][1];
 
        // Add edges
        adj[u].push(v);
        adj[v].push(u);
    }
}
 
// Function to perform DFS
// Traversal on the given tree
function DFS(node, parent, Val) {
    // Initialize answer with bitwise
    // OR of current node
    answer[node] = Val[node];
 
    // Iterate over each child
    // of the current node
    for (let child of adj[node]) {
 
        // Skip parent node
        if (child == parent)
            continue;
 
        // Call DFS for each child
        DFS(child, node, Val);
 
        // Taking bitwise OR of the
        // answer of the child to
        // find node's OR value
        answer[node] = (answer[node] | answer[child]);
    }
}
 
// Function to call DFS from the'=
// root for precomputing answers
function preprocess(Val) {
    DFS(1, -1, Val);
}
 
// Function to calculate and print
// the Bitwise OR for Q queries
function findSubtreeOR(Queries, Q, Val) {
    // Perform preprocessing
    preprocess(Val);
 
    // Iterate over each given query
    for (let i = 0; i < Q; i++) {
 
        document.write(answer[Queries[i]] + ' ');
    }
}
 
// Utility function to find and
// print bitwise OR for Q queries
function findSubtreeORUtil(N, Edges, Val, Queries, Q) {
    // Function to add edges to graph
    addEdgesToGraph(Edges, N);
 
    // Function call
    findSubtreeOR(Queries, Q, Val);
}
 
// Driver Code
 
// Number of nodes
let n = 5;
let Edges
    = [[1, 2], [1, 3],
       [3, 4], [3, 5]];
 
let Val = [0, 2, 3, 4, 8, 16];
let Queries = [2, 3, 1];
 
let Q = Queries.length;
 
// Function call
findSubtreeORUtil(n, Edges, Val, Queries, Q);
 
 
 
// This code is contributed by _saurabh_jaiswal
</script>

Output:

3 28 31

Time Complexity: O(N + Q)
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!

Queries to calculate Bitwise OR of each subtree of a given node in an N-ary Tree

C++

Java

Python3

C#

Javascript

Working with Titles and Heading – Python docx Module

Creating a Receipt Calculator using Python

One Liner for Python if-elif-else Statements

LEAVE A REPLY Cancel reply

Most Popular

YouTube Music just got the update it desperately needed, so you’ll no longer struggle to find new music or your favorites

Samsung and Apple send cease-and-desist orders to their biggest competitor

Sony apologizes, spills the tea on Xperia 1 VII fatal bug

Proton adds a safety net for your encrypted data when things go south

EDITOR PICKS

YouTube Music just got the update it desperately needed, so you’ll no longer struggle to find new music or your favorites

Samsung and Apple send cease-and-desist orders to their biggest competitor

Sony apologizes, spills the tea on Xperia 1 VII fatal bug

POPULAR POSTS

YouTube Music just got the update it desperately needed, so you’ll no longer struggle to find new music or your favorites

Samsung and Apple send cease-and-desist orders to their biggest competitor

Sony apologizes, spills the tea on Xperia 1 VII fatal bug

POPULAR CATEGORY

ABOUT US

FOLLOW US