LeetCode 2445 - Number of Nodes With Value One

LeetCode Problem 2445

Difficulty: 🟡 Medium
Topics: Array, Tree, Depth-First Search, Breadth-First Search, Binary Tree

Solution

Problem Understanding

The tree in this problem is not given explicitly through an edge list. Instead, the structure is defined mathematically. Every node v has parent floor(v / 2), which creates the same structure as a binary heap.

For example:

• Node 2 and node 3 are children of node 1
• Node 4 and node 5 are children of node 2
• Node 6 and node 7 are children of node 3

The tree contains nodes labeled from 1 to n.

Initially, every node stores the value 0.

Each query tells us to flip every value inside the subtree rooted at a specific node. Flipping means:

• 0 -> 1
• 1 -> 0

After processing all queries, we must return how many nodes contain value 1.

The key detail is that queries affect entire subtrees, not just individual nodes. Since a node may belong to multiple queried subtrees, its value depends on how many times it was flipped:

• flipped even number of times -> final value 0
• flipped odd number of times -> final value 1

The constraints are important:

• n <= 10^5
• queries.length <= 10^5

A naive approach that explicitly traverses every subtree for every query can become extremely slow. In the worst case, a subtree can contain almost all nodes, producing time complexity near O(n * q).

The problem guarantees:

• The tree is valid and connected
• Node labels are continuous from 1 to n
• Every query refers to an existing node

Important edge cases include:

• A query on the root node, which flips the entire tree
• Repeated queries on the same node
• Queries on leaf nodes
• Very deep nodes near n
• Trees that are incomplete because n may not be of the form 2^k - 1

Approaches

Brute Force Approach

The most direct solution is to explicitly simulate every query.

For each query:

1. Find all nodes in the subtree rooted at the queried node
2. Flip every node inside that subtree

We can discover subtree nodes using DFS or BFS. Since the tree follows heap indexing rules:

• left child of x is 2 * x
• right child of x is 2 * x + 1

We can recursively traverse all descendants.

This approach is correct because it directly performs the operations exactly as described in the problem statement.

However, it is too slow.

Consider:

• n = 100000
• 100000 queries
• many queries targeting large subtrees

Each query may visit almost all nodes, resulting in roughly O(n * q) operations, which can reach 10^10.

Optimal Approach

The important observation is that we do not actually need to flip subtree nodes immediately.

Instead, we can think from the perspective of each node:

A node's final value depends on how many queried subtrees contain that node.

A node belongs to the subtree of all its ancestors, including itself.

So for a node x, its value changes once for every queried ancestor of x.

This leads to a much more efficient strategy:

1. Count how many times each node appears in queries
2. Perform a DFS from the root
3. While traversing downward, maintain the cumulative number of flips inherited from ancestors
4. If the cumulative flip count is odd, the current node ends as 1

This works because subtree flips propagate naturally downward through ancestor relationships.

Approach	Time Complexity	Space Complexity	Notes
Brute Force	O(n * q)	O(n)	Explicitly flips every subtree
Optimal	O(n + q)	O(n)	Uses cumulative flip propagation during DFS

Algorithm Walkthrough

1. Create an array called flip_count of size n + 1.

flip_count[x] stores how many queries directly target node x. 2. Process all queries.

For each query node q, increment:

flip_count[q] += 1

We do not flip anything yet. We only record how many flips originate at each node. 3. Start DFS from the root node 1.

During DFS, maintain a variable called current_flips.

This represents how many flips affect the current node from all ancestors encountered so far. 4. When visiting node x, compute:

total_flips = current_flips + flip_count[x]

This includes:

• flips inherited from ancestors
• flips initiated at the current node

5. Determine the final value of node x.

If total_flips is odd, the node ends with value 1.

If it is even, the node ends with value 0. 6. Recursively visit children.

Since this is a heap-style tree:

• left child = 2 * x
• right child = 2 * x + 1

Only recurse if the child label is <= n. 7. Pass total_flips downward.

Every descendant inherits all flips affecting the current node. 8. Count how many nodes finish with odd flip counts.

Return this count after DFS completes.

Why it works

A subtree flip affects exactly all descendants of the queried node, including itself. During DFS, every node accumulates all flips originating from its ancestors. Since a node belongs precisely to the subtrees rooted at its ancestors, the cumulative flip count exactly equals the number of times the node should be flipped. A node ends as 1 if and only if that count is odd.

Python Solution

from typing import List

class Solution:
    def numberOfNodes(self, n: int, queries: List[int]) -> int:
        flip_count = [0] * (n + 1)

        for node in queries:
            flip_count[node] += 1

        result = 0

        def dfs(node: int, inherited_flips: int) -> None:
            nonlocal result

            if node > n:
                return

            total_flips = inherited_flips + flip_count[node]

            if total_flips % 2 == 1:
                result += 1

            dfs(node * 2, total_flips)
            dfs(node * 2 + 1, total_flips)

        dfs(1, 0)

        return result

The implementation begins by counting how many flip operations originate at each node. Instead of simulating subtree updates immediately, the algorithm postpones all work until DFS traversal.

The recursive DFS function receives two parameters:

• node, the current node label
• inherited_flips, the number of flips passed down from ancestors

At every node, the algorithm adds locally initiated flips using:

total_flips = inherited_flips + flip_count[node]

If total_flips is odd, the node finishes with value 1, so the result counter increases.

The recursion then propagates the updated flip count to both children. Because every descendant inherits all ancestor flips, this naturally models subtree operations without explicitly modifying subtree nodes.

The recursion stops whenever a node label exceeds n, since such nodes do not exist in the tree.

Go Solution

func numberOfNodes(n int, queries []int) int {
    flipCount := make([]int, n+1)

    for _, node := range queries {
        flipCount[node]++
    }

    result := 0

    var dfs func(int, int)

    dfs = func(node int, inheritedFlips int) {
        if node > n {
            return
        }

        totalFlips := inheritedFlips + flipCount[node]

        if totalFlips%2 == 1 {
            result++
        }

        dfs(node*2, totalFlips)
        dfs(node*2+1, totalFlips)
    }

    dfs(1, 0)

    return result
}

The Go implementation follows the same logic as the Python version.

Some Go-specific details:

• Slices are used instead of Python lists
• Recursive functions are declared using function variables
• Integer overflow is not a concern because values remain within standard integer limits
• Go does not have nonlocal, so result is captured naturally by the closure

Worked Examples

Example 1

n = 5
queries = [1, 2, 5]

Tree structure:

        1
      /   \
     2     3
    / \
   4   5

Step 1: Build flip count

Node	flip_count
1	1
2	1
3	0
4	0
5	1

Step 2: DFS Traversal

Current Node	Inherited Flips	Local Flips	Total Flips	Final Value
1	0	1	1	1
2	1	1	2	0
4	2	0	2	0
5	2	1	3	1
3	1	0	1	1

Nodes with value 1 are:

1, 3, 5

Final answer:

3

Example 2

n = 3
queries = [2, 3, 3]

Tree structure:

    1
   / \
  2   3

Step 1: Build flip count

Node	flip_count
1	0
2	1
3	2

Step 2: DFS Traversal

Current Node	Inherited Flips	Local Flips	Total Flips	Final Value
1	0	0	0	0
2	0	1	1	1
3	0	2	2	0

Only node 2 ends with value 1.

Final answer:

1

Complexity Analysis

Measure	Complexity	Explanation
Time	O(n + q)	One pass over queries and one DFS traversal over all nodes
Space	O(n)	Flip count array plus recursion stack

The algorithm processes every query exactly once and visits every node exactly once during DFS. No subtree is traversed repeatedly, which eliminates the inefficiency of the brute force approach.

The recursion depth depends on tree height, which is O(log n) for this heap-structured tree, but the flip count array requires O(n) memory.

Test Cases

from typing import List

class Solution:
    def numberOfNodes(self, n: int, queries: List[int]) -> int:
        flip_count = [0] * (n + 1)

        for node in queries:
            flip_count[node] += 1

        result = 0

        def dfs(node: int, inherited_flips: int) -> None:
            nonlocal result

            if node > n:
                return

            total_flips = inherited_flips + flip_count[node]

            if total_flips % 2 == 1:
                result += 1

            dfs(node * 2, total_flips)
            dfs(node * 2 + 1, total_flips)

        dfs(1, 0)

        return result

sol = Solution()

assert sol.numberOfNodes(5, [1, 2, 5]) == 3  # provided example 1
assert sol.numberOfNodes(3, [2, 3, 3]) == 1  # provided example 2

assert sol.numberOfNodes(1, [1]) == 1  # single node flipped once
assert sol.numberOfNodes(1, [1, 1]) == 0  # single node flipped twice

assert sol.numberOfNodes(7, [1]) == 7  # entire tree flipped once
assert sol.numberOfNodes(7, [1, 1]) == 0  # entire tree flipped twice

assert sol.numberOfNodes(7, [4]) == 1  # leaf node only
assert sol.numberOfNodes(7, [2]) == 3  # subtree rooted at node 2

assert sol.numberOfNodes(15, [2, 2, 2]) == 7  # odd repeated flips
assert sol.numberOfNodes(15, [2, 2]) == 0  # even repeated flips

assert sol.numberOfNodes(10, [10]) == 1  # deepest node flip
assert sol.numberOfNodes(10, [5, 10]) == 1  # overlapping subtree effects

Test	Why
n=5, [1,2,5]	Validates example 1
n=3, [2,3,3]	Validates example 2
n=1, [1]	Smallest possible tree
n=1, [1,1]	Double flip cancellation
n=7, [1]	Entire tree flip
n=7, [1,1]	Entire tree restored
n=7, [4]	Leaf-only subtree
n=7, [2]	Internal subtree flip
n=15, [2,2,2]	Odd repeated subtree flips
n=15, [2,2]	Even repeated subtree flips
n=10, [10]	Deep incomplete-tree node
n=10, [5,10]	Overlapping subtree behavior

Edge Cases

One important edge case occurs when the root node is queried. Since the root's subtree contains the entire tree, every node must flip. A naive implementation might repeatedly traverse the whole tree for such queries, causing severe performance problems. The optimized solution handles this naturally because the root's flip count is simply propagated to all descendants during DFS.

Another important case involves repeated queries on the same node. Since flipping twice cancels out, implementations that directly toggle values may become error-prone or inefficient. The algorithm avoids this issue entirely by tracking flip counts mathematically and checking parity using total_flips % 2.

A third edge case appears when n does not form a perfect binary tree. For example, n = 10 means some potential children do not exist. Recursive traversal must carefully stop whenever a child label exceeds n. The implementation explicitly checks this condition before processing nodes, preventing invalid accesses.

A final subtle case involves leaf nodes. A leaf subtree contains only the node itself. Some implementations incorrectly assume every node has children and may attempt invalid recursion. The boundary condition if node > n: return ensures that nonexistent children are safely ignored.