Find Elements in a Contaminated Binary Tree

medium tree design hash set bfs

Problem

You are given a binary tree whose every node value was overwritten with -1 (it is "contaminated"). The original tree followed a fixed rule: the root holds 0, and for any node holding x its left child holds 2x + 1 and its right child holds 2x + 2. First recover the original values, then build a structure that answers queries: does the recovered tree contain a given target value? Each call to find(target) returns true or false.

Inputtree = [-1, null, -1], find(1), find(2)

Output[false, true]

Recover: root → 0; it has only a right child → that child becomes 2·0 + 2 = 2. The recovered values are {0, 2}. So find(1) is false and find(2) is true.

tree (level-order, "_" or "null" = missing)

find target

class FindElements:
    def __init__(self, root):
        self.seen = set()
        def recover(node, val):
            if not node:
                return
            self.seen.add(val)
            recover(node.left, 2 * val + 1)
            recover(node.right, 2 * val + 2)
        recover(root, 0)

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

class FindElements {
  constructor(root) {
    this.seen = new Set();
    const recover = (node, val) => {
      if (!node) return;
      this.seen.add(val);
      recover(node.left, 2 * val + 1);
      recover(node.right, 2 * val + 2);
    };
    recover(root, 0);
  }
  find(target) {
    return this.seen.has(target);
  }
}

class FindElements {
    private Set<Integer> seen = new HashSet<>();
    public FindElements(TreeNode root) {
        recover(root, 0);
    }
    private void recover(TreeNode node, int val) {
        if (node == null) return;
        seen.add(val);
        recover(node.left, 2 * val + 1);
        recover(node.right, 2 * val + 2);
    }
    public boolean find(int target) {
        return seen.contains(target);
    }
}

class FindElements {
    unordered_set<int> seen;
    void recover(TreeNode* node, int val) {
        if (!node) return;
        seen.insert(val);
        recover(node->left, 2 * val + 1);
        recover(node->right, 2 * val + 2);
    }
public:
    FindElements(TreeNode* root) { recover(root, 0); }
    bool find(int target) {
        return seen.count(target) > 0;
    }
};

Explanation

The values are all wiped to -1, but the shape of the tree is intact. Since the original numbering was a fixed formula, the shape alone tells us every original value: walk the tree and recompute each value from its parent.

The rule is: the root is 0; a node holding x gives its left child 2x + 1 and its right child 2x + 2. So we do one traversal starting at the root with value 0, and at every real node we record the computed value in a hash set called seen.

Once the set is built, answering a query is trivial: find(target) just checks whether target is in seen, which is an O(1) lookup. We pay the recovery cost only once, in the constructor, and every later query is instant.

Example on [-1, _, -1]: start at the root with value 0 and add it. The root has no left child, but it does have a right child, which gets 2·0 + 2 = 2 — add that too. The set is {0, 2}. Now find(1) is false (1 was never produced) and find(2) is true.

You can do the recovery with depth-first recursion (as shown) or with a breadth-first queue carrying each node's recovered value — both visit every node exactly once.

Time: O(n) build, O(1) per find Space: O(n)