Number of Nodes With Value One

Number of Nodes With Value One

What is this problem about?

The Number of Nodes With Value One problem presents a binary tree with queries. Each query flips all nodes on the path from the root to a given node. After all queries, count the number of nodes with value 1 (starting all at 0). This coding problem uses the observation that a node's final value equals the parity of how many query paths pass through it.

Why is this asked in interviews?

Infosys asks this to test the ability to model path-flip operations efficiently. The key insight: a node at depth d is on the path to node v if v's ancestor at the same depth is the node itself. A node's value = (number of queries whose path includes it) % 2. The BFS, DFS, binary tree, and tree interview pattern is the core.

Algorithmic pattern used

Ancestor query counting via DFS. For each node, count how many queries have that node on their root-to-node path. A query for node q includes node u if u is an ancestor of q. Equivalently, for each query q, all ancestors of q (including q itself) get flipped. Use DFS to propagate a flip count down the tree: when a query targets node q, increment a counter at q, then let the DFS propagate this count to children, and a node's total flip count = sum of its ancestor flip counts.

Example explanation

Tree: 1→(2,3)→(4,5,6,7). Queries: [1,2,3].

• Query 1: flips nodes 1.
• Query 2: flips nodes 1,2.
• Query 3: flips nodes 1,3. Node 1 flip count: 3 (odd) → value=1. Node 2 flip count: 2 (even) → value=0. Node 3 flip count: 2 → value=0. Nodes 4,5,6,7: flip count=1 each → value=1. Count of value-1 nodes = 5.

Common mistakes candidates make

• Simulating every flip operation individually (too slow for many queries).
• Not recognizing that ancestors share the query's flip count.
• Using BFS which doesn't naturally propagate ancestral counts.
• Off-by-one in counting the queried node itself (it's on its own path).

Interview preparation tip

Tree path-flip problems often reduce to "count queries that include each node." Once you model it as "count ancestral queries," a single DFS with a running counter efficiently computes each node's total flip count. Practice similar "range update on a tree path" problems — they generalize to heavy-light decomposition for harder queries. Understanding parity (even flips = stays 0, odd = becomes 1) is the final logical step.