Domain 2MediumMEDIUM

Find Elements in a Contaminated Binary Tree

Recover a contaminated binary tree by calculating node values based on parent-child relationships and store them in a hash set for O(1) lookup during queries.

Domain: medium•Updated: 2026-09-13
#hash set#binary tree traversal#O(N) time complexity#pre-computation

Problem Breakdown

We are given a Binary Tree where all TreeNode.val attributes have been corrupted to -1. We must recover the tree structure by calculating the correct integer value for every node based on two rules:

  1. The root always starts at 0.
  2. For any node with value xx, its left child is 2x+12x + 1 and right child is 2x+22x + 2.

After recovery, we need to efficiently check if a specific target integer exists in the recovered tree values. This involves two phases: Recovery (traversing once) and Querying (checking existence). Given frequent queries (MM calls), storing all valid node values in a Hash Set allows for constant-time lookups, shifting complexity from O(H×M)O(H \times M) to O(N+M)O(N + M).

Intuition

A naive approach would calculate the value of a target path during every find operation by traversing from the root. While technically fast enough given height constraints (H≤20H \le 20), it ignores the fact that we have already “recovered” the tree structure during initialization. The key insight for optimization is Pre-computation. Since find operations are frequent and independent, we should perform all necessary work in the constructor (__init__). By calculating every node’s value once using a traversal (DFS or BFS) and storing them in a Hash Set (O(1)O(1) average lookup), we shift complexity from O(H×M)O(H \times M) to O(N+M)O(N + M), where NN is nodes and MM is queries.

Approach

  1. Initialization (__init__):

    • Create an empty set self.seen.
    • Handle the edge case if root is None (though constraints guarantee at least one node).
    • Set root.val = 0 immediately as per rules and add to self.seen.
    • Use a traversal (DFS using stack or BFS using queue) starting from the root.
    • For each visited node, calculate left child value (2×val+12 \times val + 1) and right child value (2×val+22 \times val + 2).
    • If a child exists in the tree structure: update its .val, add it to self.seen.
    • Continue until all reachable nodes are visited.
  2. Query (find):

    • Simply check if target is present in self.seen. Return boolean result immediately (O(1)O(1)).

Complexity Analysis

  • Time:
    • Initialization: O(N)O(N) where NN is the number of nodes (we visit each node once to set values and insert into hash map).
    • Find operation: O(1)O(1) average time complexity due to Hash Set lookup.
    • Total for all operations: O(N+M)O(N + M).
  • Space:
    • We store every valid value in a HashSet, so space is proportional to the number of nodes present in the tree (O(N)O(N)).

Solution

class FindElements:
    def __init__(self, root):
        self.seen = set()
        
        # Handle edge case where root might be None (though constraints say N >= 1)
        if not root: 
            return
        
        # Start with the rule that root must be 0
        root.val = 0
        self.seen.add(0)

        stack = [root]
        
        while stack:
            node = stack.pop()
            
            left_child = node.left
            right_child = node.right
            
            if left_child:
                val_left = node.val * 2 + 1
                left_child.val = val_left
                self.seen.add(val_left)
                stack.append(left_child)
                
            if right_child:
                val_right = node.val * 2 + 2
                right_child.val = val_right
                self.seen.add(val_right)
                stack.append(right_child)

    def find(self, target):
        return target in self.seen

Edge Cases Handled

  • Empty Tree: Constraints specify at least one node (1≤N1 \le N), but the code handles root checks implicitly via logic. If root were None, stack would be empty and loop skipped safely (though constraints prevent this).
  • Missing Children: The traversal explicitly checks if left_child or right_child exists before calculating values to avoid errors on null pointers.
  • Large Targets: Python handles large integers automatically; the set lookup works regardless of magnitude as long as it fits in memory, which is guaranteed by constraints (10610^6).
  • Unique Values: In this specific tree generation rule (binary representation), every node has a unique value relative to its position. The Set naturally ensures uniqueness checks are O(1)O(1).