2445. Number of Nodes With Value One


Problem Description

In this problem, we are given a binary tree with n number of nodes labeled from 1 to n. The tree is connected, undirected, and, importantly, each node's parent is defined by the floor division of its label by 2, where the floor function returns the greatest integer less than or equal to its argument. For instance, floor(3/2) is 1. This layout suggests that every node (except the root, labeled 1) has exactly one parent, and node 1 is the root of the tree.

The objective is to process a series of queries. Each query corresponds to a node's label, and the query's operation is to flip the value of all nodes in the subtree rooted at the given node's label. Flipping a value means that if a node's value is 0, it becomes 1, and vice versa. Initially, all nodes have a value of 0.

Our goal is to determine the total number of nodes with the value 1 after processing all queries. A query might be repeated, and if a node's value is flipped an odd number of times, it ends up with a value of 1.

Intuition

To solve this problem, we take a stepwise approach. The total number of flips on a single node equals the number of times this node appeared in the queries. So, we first count the occurrences of each node in the queries using a frequency counter.

Next, we iterate over our counter, and for each node that has been queried an odd number of times (since an even number of flips would cancel out), we perform the flip operation on that node's subtree.

To flip a node's subtree iteratively, we use a depth-first search (DFS) strategy. Starting from the given node (which appears in queries), we recursively flip the current node's value and then perform the same operation on its left and right children, which are located at indices 2*i and 2*i+1 respectively in a binary tree context. Given that it's a binary tree, each node could have up to two children, and this is fulfilled through bit manipulation: the left child is at index i << 1, and the right child is at index i << 1 | 1.

After processing all relevant queries, we sum up the values in the tree array to find the total count of nodes with value 1.

This method works efficiently because we only perform subtree flips for nodes that were affected by an odd number of queries. We also avoid redundant work by skipping the count of nodes that would ultimately have a value of 0 after an even number of flips.

Solution Approach

The implementation of the solution aligns with the intuition described and makes use of a simple recursive depth-first search (DFS) algorithm along with bitwise manipulation techniques, as follows:

  1. Counter Collection: We initiate by creating a Counter object for collecting the frequency of each node in the queries. The Counter is well-suited for this task as it efficiently tallies the counts with minimal manual bookkeeping.

  2. Tree Initialization: A tree array is initialized with n + 1 elements, all set to 0. This extra element accounts for the 1-based node labeling. Each index i of the array will represent the value of the respective node labeled i.

  3. DFS Function: A nested DFS function, dfs(i), is defined to flip the subtree starting from node i. The function first checks if the node i is within bounds (i.e., does not exceed n). It then flips the value at tree[i] using tree[i] ^= 1 (bitwise XOR operation), where flipping is done effectively by XOR-ing the current value with 1. After that, recursive calls are made to flip the left and right children of the node i using dfs(i << 1) and dfs(i << 1 | 1) respectively. The left shift operator (<<) doubles the index, representing the left child, and the bitwise OR with 1 (| 1) obtains the right child's index.

  4. Processing Queries: We iterate over the items in the Counter, checking each node label and associated count. If the count is odd (checked using v & 1), we call the dfs(i) function to flip the subtree rooted at that node.

  5. Summing the Values: After processing all queries, we sum up the tree array, excluding the zero index (as it's not used), to get the total number of nodes that have a value of 1.

This algorithm traverses the tree only once for every node that needs to be flipped, resulting in a time complexity proportional to the number of queries and the size of the subtrees that need to be flipped. Space complexity is linear to the size of the tree since we maintain an array of size n + 1.

Here is a breakdown of the main components in the code:

1cnt = Counter(queries)  # Using Counter to tally queries
2tree = [0] * (n + 1)  # Tree array initialized
3
4def dfs(i):  # Recursive DFS definition
5    if i > n:  # Check bounds
6        return
7    tree[i] ^= 1  # Flip current value
8    dfs(i << 1)  # Recur left
9    dfs(i << 1 | 1)  # Recur right
10
11for i, v in cnt.items():
12    if v & 1:  # Is the count odd?
13        dfs(i)  # Flip subtree if needed
14
15return sum(tree)  # Sum the tree values for the result

The use of bitwise operations for index calculation and value flipping makes the implementation succinct and efficient.

Example Walkthrough

Let's consider a binary tree with 3 nodes. Now, here are the steps to illustrate the solution approach:

Step 1: Queries Counter Collection

Suppose we have queries with node labels [2, 1, 2]. Using a Counter, we count the occurrences: {1: 1, 2: 2}.

Step 2: Tree Initialization

We initialize our tree with n + 1 elements all set to 0, resulting in tree = [0, 0, 0, 0].

Step 3: Define DFS Function

We define a dfs function that flips the value of a node and recursively does the same for its children.

Step 4: Processing Queries with DFS

According to the Counter, node 1 has been queried once, and node 2 has been queried twice. Queried node 2 is even, so flipping it twice will bring it back to 0. Node 1 is odd, so we flip it and its subtree.

Flipping Node 1 and Its Subtree:
  • Flip node 1: tree = [0, 1, 0, 0]
  • Flip its left child (2*1 = 2): tree = [0, 1, 1, 0]
  • Flip its right child (2*1 + 1 = 3): tree = [0, 1, 1, 1]

Step 5: Summing the Values

Now, we sum up values from index 1 onwards to find the number of nodes with value 1: sum(tree[1:]), which gives us 3.

The result is 3, meaning after processing all queries, there are 3 nodes with the value 1.

This example illustrates how the given solution processes the nodes and their respective subtrees based on the queries, flip operation, and the use of DFS in an efficient manner.

Python Solution

1from collections import Counter
2
3class Solution:
4    def numberOfNodes(self, n: int, queries: List[int]) -> int:
5        # Helper function to switch the state of the nodes in the tree.
6        # It performs a depth-first search to toggle each node starting from index i.
7        def toggle_nodes_dfs(index):
8            # Base case: if the index is greater than n, return since it's not a valid node.
9            if index > n:
10                return
11            # Toggle the current node's state.
12            tree[index] ^= 1
13            # Recursively toggle the state of the left child.
14            toggle_nodes_dfs(index << 1)
15            # Recursively toggle the state of the right child.
16            toggle_nodes_dfs(index << 1 | 1)
17
18        # Initialize the tree with 0s, each index represents a node, and the state is off (0).
19        tree = [0] * (n + 1)
20        # Count the occurrences of each query.
21        query_counts = Counter(queries)
22        # Iterate over items in query_counts to perform toggles for odd counts.
23        for index, frequency in query_counts.items():
24            # If the frequency of toggles is odd, we need to perform the toggle operations.
25            if frequency & 1:
26                toggle_nodes_dfs(index)
27      
28        # Sum up all the nodes' states to get the total number of nodes that are on (1).
29        return sum(tree)
30

Java Solution

1class Solution {
2    // The 'tree' array represents a binary tree where each node can have two states: 0 or 1.
3    private int[] tree;
4
5    // Method to calculate the number of nodes with state 1 after processing the queries.
6    public int numberOfNodes(int n, int[] queries) {
7        // Initialize the tree to have 'n + 1' nodes (indexing from 0 to n).
8        tree = new int[n + 1];
9        // Array to keep count of occurrences of each value in queries.
10        int[] count = new int[n + 1];
11        // Count the occurrences of each value in the queries.
12        for (int value : queries) {
13            ++count[value];
14        }
15        // Toggle the state of each node with an odd count.
16        for (int i = 0; i < n + 1; ++i) {
17            if (counter[i] % 2 == 1) {
18                dfs(i); // Perform a depth-first search starting from node 'i'.
19            }
20        }
21        // Calculate the answer by summing up the states of all nodes.
22        int answer = 0;
23        for (int i = 0; i < n + 1; ++i) {
24            answer += tree[i];
25        }
26        return answer;
27    }
28
29    // Helper method to toggle the states of the current node and its children.
30    private void dfs(int index) {
31        // If the index is beyond the length of the tree array, end the recursion.
32        if (index >= tree.length) {
33            return;
34        }
35        // Toggle the current node's state.
36        tree[index] ^= 1;
37        // Recursively toggle the states of the left and right children nodes (if they exist).
38        dfs(index << 1);       // Left child index is current index shifted one bit to the left.
39        dfs(index << 1 | 1);   // Right child index is left child index with a bit-wise OR with 1.
40    }
41}
42

C++ Solution

1#include <vector>
2#include <numeric> // For std::accumulate
3#include <functional> // For std::function
4
5class Solution {
6public:
7    // Function to count the number of nodes set to '1' in a binary tree 
8    // after applying the queries.
9    int numberOfNodes(int n, std::vector<int>& queries) {
10        std::vector<int> tree(n + 1, 0); // Tree array to keep track of node status (0 or 1).
11        std::vector<int> count(n + 1, 0); // Count array to record the number of times each node is queried.
12      
13        // Increment count for each query value.
14        for (int value : queries) ++count[value];
15      
16        // Recursive function to toggle the status of nodes.
17        std::function<void(int)> toggleNodes = [&](int index) {
18            if (index > n) return; // Base case for recursion: index out of bounds.
19            tree[index] ^= 1; // Toggle the node status using XOR operation.
20            toggleNodes(index << 1); // Recurse for the left child.
21            toggleNodes(index << 1 | 1); // Recurse for the right child.
22        };
23      
24        // Apply the queries to the tree according to the count.
25        for (int i = 0; i < n + 1; ++i) {
26            // If the count is odd, toggle the node status.
27            if (count[i] & 1) {
28                toggleNodes(i);
29            }
30        }
31      
32        // Sum up the values in the tree array to count the nodes that are set to '1'.
33        return std::accumulate(tree.begin(), tree.end(), 0);
34    }
35};
36

Typescript Solution

1// Function to count the number of nodes set to '1' in a binary tree 
2// after applying the queries.
3function numberOfNodes(n: number, queries: number[]): number {
4    // Tree array to keep track of node status (0 or 1).
5    let tree: number[] = new Array(n + 1).fill(0);
6    // Count array to record the number of times each node is queried.
7    let count: number[] = new Array(n + 1).fill(0);
8
9    // Increment count for each query value.
10    for (let value of queries) count[value]++;
11
12    // Recursive function to toggle the status of nodes.
13    let toggleNodes = (index: number) => {
14        if (index > n) return; // Base case for recursion: index out of bounds.
15        tree[index] ^= 1; // Toggle the node status using XOR operation.
16        toggleNodes(index << 1); // Recurse for the left child.
17        toggleNodes(index << 1 | 1); // Recurse for the right child.
18    };
19
20    // Apply the queries to the tree according to the count.
21    for (let i = 0; i <= n; i++) {
22        // If the count is odd, toggle the node status.
23        if (count[i] % 2 === 1) {
24            toggleNodes(i);
25        }
26    }
27
28    // Sum up the values in the tree array to count the nodes that are set to '1'.
29    return tree.reduce((accumulator, currentValue) => accumulator + currentValue, 0);
30}
31
32export { numberOfNodes }; // Optionally, export the function to be used in other modules.
33

Time and Space Complexity

Time Complexity

The time complexity of the given code is determined by the number of times the dfs function is called, which depends on the structure of the tree and how many times each node is toggled.

  1. The tree has n nodes and in the worst-case scenario, for a complete binary tree, the dfs function would perform a full traversal to toggle nodes below it.
  2. Each query potentially leads to a full traversal from the current node to all nodes below it.
  3. If a node is toggled an even number of times, it ends up in its original state. Only nodes toggled an odd number of times will affect the final count.

Considering these points:

  • The maximum height of the tree is log2(n) and the maximum number of nodes at the last level is n/2 (in a complete binary tree).
  • For each toggle operation, in the worst-case scenario, we may have to visit all nodes of the subtree rooted at the given node.
  • The maximum number of operations for a single query is O(n) since in the worst case we may need to toggle all nodes in the tree.

Assuming m is the number of unique queries, the worst-case time complexity for odd-toggled nodes is O(m * n), as every query can potentially result in traversing and toggling the entire tree.

Space Complexity

The space complexity depends on:

  1. The tree array, which requires O(n) space to store the toggle state of each node.
  2. The recursion stack for the dfs function, which in the worst-case scenario, may go up to O(log n) in depth for a balanced binary tree due to the binary tree's height.
  3. The Counter object, which stores the counts of each query. In the worst case, if all queries are unique, it requires O(m) space.

Hence, the overall space complexity is O(n + log n + m). However, since m can at most be n (if all nodes are queried once), and log n is lesser than n, the more dominant term is O(n), which simplifies our space complexity to O(n).


Got a question? Ask the Teaching Assistant anything you don't understand.

Still not clear? Ask in the Forum,  Discord or Submit the part you don't understand to our editors.


TA 👨‍🏫