Skip to main content
Talentd

Number of Nodes With Value One - Solution & Explanation

MediumPremiumFree on FleetCodeTreeDepth-First SearchBreadth-First SearchBinary Tree8 min readAsked at: Infosys
Practice this problem

Problem Statement

There is an undirected connected tree with n nodes labeled from 1 to n and n - 1 edges. You are given the integer n. The parent node of a node with a label v is the node with the label floor (v / 2). The root of the tree is the node with the label 1.

  • For example, if n = 7, then the node with the label 3 has the node with the label floor(3 / 2) = 1 as its parent, and the node with the label 7 has the node with the label floor(7 / 2) = 3 as its parent.

You are also given an integer array queries. Initially, every node has a value 0 on it. For each query queries[i], you should flip all values in the subtree of the node with the label queries[i].

Return the total number of nodes with the value 1 after processing all the queries.

Note that:

  • Flipping the value of a node means that the node with the value 0 becomes 1 and vice versa.
  • floor(x) is equivalent to rounding x down to the nearest integer.

 

Example 1:

Input: n = 5 , queries = [1,2,5]
Output: 3
Explanation: The diagram above shows the tree structure and its status after performing the queries. The blue node represents the value 0, and the red node represents the value 1.
After processing the queries, there are three red nodes (nodes with value 1): 1, 3, and 5.

Example 2:

Input: n = 3, queries = [2,3,3]
Output: 1
Explanation: The diagram above shows the tree structure and its status after performing the queries. The blue node represents the value 0, and the red node represents the value 1.
After processing the queries, there are one red node (node with value 1): 2.

 

Constraints:

  • 1 <= n <= 105
  • 1 <= queries.length <= 105
  • 1 <= queries[i] <= n

Approach Overview

Problem Overview: You have a complete binary tree with n nodes labeled from 1 to n. Every node initially holds value 0. Each query flips the value of every node in the subtree rooted at a given node. After processing all queries, return how many nodes end up with value 1.

Approach 1: Brute Force Subtree Traversal (O(n * q) time, O(n) space)

Directly simulate each query. For a query node x, traverse its entire subtree and toggle the value of every node encountered. In a complete binary tree, children of node i are 2*i and 2*i + 1, so you can run a DFS or BFS from x and flip values while staying within the range 1..n. This works but becomes expensive when the subtree is large or the number of queries grows. In the worst case, each query may touch nearly all nodes, leading to O(n * q) time complexity and O(n) space for the tree state. This approach demonstrates the problem mechanics but usually exceeds time limits for large inputs. Traversal can be implemented using Depth-First Search or Breadth-First Search.

Approach 2: Simulation with Ancestor Traversal (O(n log n) time, O(q) space)

A key observation: a node's final value depends on how many queries targeted its ancestors. If a query flips the subtree rooted at node a, then every descendant of a is toggled once. For a node v, you only need to check the path from v up to the root and count how many of those nodes appear in the query list.

Store all query nodes in a hash set. Then iterate through every node 1..n. For each node, repeatedly move to its parent using i = i // 2 (property of a complete Binary Tree). If any ancestor appears in the query set, that represents a flip affecting this node. Track the number of flips along the path; if the count is odd, the node's final value is 1.

The height of a complete binary tree is O(log n), so each node performs at most log n ancestor checks. Iterating across all nodes results in O(n log n) time complexity and O(q) space for storing the query set. This approach avoids explicitly traversing subtrees and works efficiently for large inputs.

Recommended for interviews: The ancestor-check simulation is the expected solution. Brute force traversal proves you understand subtree operations, but recognizing that each node only depends on flips from its ancestors reduces the work from repeated subtree scans to simple upward traversal.

Solution

According to the problem description, we can simulate the process of each query, that is, reverse the values of the query node and its subtree nodes. Finally, count the number of nodes with a value of 1.

There is an optimization point here. If a node and its corresponding subtree have been queried an even number of times, the node value will not change. Therefore, we can record the number of queries for each node, and only reverse the nodes and their subtrees that have been queried an odd number of times.

The time complexity is O(n times log n), and the space complexity is O(n). Here, n is the number of nodes.

Code

PythonJavaC++Go

Python

Java

C++

Go

Try this approach in the editor →

Detailed Complexity Analysis

ApproachTimeSpaceWhen to Use
Brute Force Subtree TraversalO(n * q)O(n)Useful for understanding subtree flipping or when constraints are very small
Simulation with Ancestor TraversalO(n log n)O(q)General case; avoids repeated subtree traversals by checking ancestor flips

Video Solution

LeetCode Medium - 2445. Number of Nodes With Value One • robzingcod • 91 views views

Frequently Asked Questions

Is Number of Nodes With Value One easy or hard?
Number of Nodes With Value One is rated Medium. The challenge is recognizing that subtree flips can be evaluated by checking ancestor queries instead of explicitly updating every node in each subtree.
Number of Nodes With Value One Python/Java solution
The typical implementation stores queries in a set and iterates through nodes from 1 to n. For each node, move upward using integer division by 2 while counting how many ancestor nodes appear in the set. The same logic works in Python, Java, C++, and Go with O(n log n) time complexity.
How to solve Number of Nodes With Value One in O(n log n)?
Store the query nodes in a hash set. For each node from 1 to n, repeatedly move to its parent using index // 2 while counting how many ancestors exist in the query set. If the number of flips is odd, that node's value becomes 1. Since each upward traversal is at most log n steps, the total runtime is O(n log n).
What is the best approach for Number of Nodes With Value One?
The most practical approach is simulation using ancestor traversal. Store all query nodes in a hash set, then for each node walk up the parent chain to the root and count how many queries affect it. If the number of flips is odd, the node ends with value 1. This runs in O(n log n) time because the height of a complete binary tree is logarithmic.
Is Number of Nodes With Value One asked at Google/Amazon/Meta?
Problems involving subtree updates, binary tree indexing, and flip parity appear frequently in interviews at companies like Amazon, Google, and Meta. Variants often test your understanding of tree traversal, ancestor relationships, and optimization of repeated subtree operations.
What data structure is used in Number of Nodes With Value One?
The main structures are a hash set to store query nodes and implicit binary tree indexing using the complete tree property. Parent lookup uses the formula i // 2, which eliminates the need to build an explicit tree structure.
What is the time complexity of Number of Nodes With Value One?
The optimized simulation approach runs in O(n log n) time and O(q) space. Each of the n nodes checks at most log n ancestors while verifying whether any of them appear in the query set. A naive subtree traversal solution can degrade to O(n * q) time.

Ready to solve this problem?

Practice Number of Nodes With Value One with our built-in code editor and test cases.

Practice on FleetCode
Previous

Binary Tree Inorder Traversal

Next

Unique Binary Search Trees II