Watch the video solution for Number of Nodes With Value One, a medium level problem involving Tree, Depth-First Search, Breadth-First Search. This walkthrough by robzingcod has 89 views views. Want to try solving it yourself? Practice on FleetCode or read the detailed text solution.
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.
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:
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 <= 1051 <= queries.length <= 1051 <= queries[i] <= nProblem 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.
| Approach | Time | Space | When to Use |
|---|---|---|---|
| Brute Force Subtree Traversal | O(n * q) | O(n) | Useful for understanding subtree flipping or when constraints are very small |
| Simulation with Ancestor Traversal | O(n log n) | O(q) | General case; avoids repeated subtree traversals by checking ancestor flips |