Most Optimal Solution ✅BFS | C++| Java | Python | JavaScript
⬆️Upvote if it helps ⬆️Connect with me on Linkedin [Bijoy Sing]IntuitionThe given binary tree is "contaminated" with all values set to-1. However, we know the o
# ⬆️Upvote if it helps ⬆️

---

## Connect with me on Linkedin [Bijoy Sing]

---

```cpp []
class Solution {
public:
    unordered_set<int> values;

    Solution(TreeNode* root) {
        if (!root) return;
        queue<pair<TreeNode*, int>> q;
        q.push({root, 0});

        while (!q.empty()) {
            auto [node, val] = q.front();
            q.pop();
            node->val = val;
            values.insert(val);

            if (node->left) q.push({node->left, 2 * val + 1});
            if (node->right) q.push({node->right, 2 * val + 2});
        }
    }

    bool find(int target) {
        return values.count(target);
    }
};
```

```python []
class Solution:
    def __init__(self, root):
        self.values = set()
        if not root:
            return
        queue = [(root, 0)]

        while queue:
            node, val = queue.pop(0)
            node.val = val
            self.values.add(val)

            if node.left:
                queue.append((node.left, 2 * val + 1))
            if node.right:
                queue.append((node.right, 2 * val + 2))

    def find(self, target):
        return target in self.values
```

```java []
import java.util.*;

class Solution {
    private Set<Integer> values = new HashSet<>();

    public Solution(TreeNode root) {
        if (root == null) return;
        Queue<Pair<TreeNode, Integer>> queue = new LinkedList<>();
        queue.add(new Pair<>(root, 0));

        while (!queue.isEmpty()) {
            Pair<TreeNode, Integer> pair = queue.poll();
            TreeNode node = pair.getKey();
            int val = pair.getValue();
            node.val = val;
            values.add(val);

            if (node.left != null) queue.add(new Pair<>(node.left, 2 * val + 1));
            if (node.right != null) queue.add(new Pair<>(node.right, 2 * val + 2));
        }
    }

    public boolean find(int target) {
        return values.contains(target);
    }
}
```

```javascript []
class Solution {
    constructor(root) {
        this.values = new Set();
        if (!root) return;
        let queue = [[root, 0]];

        while (queue.length > 0) {
            let [node, val] = queue.shift();
            node.val = val;
            this.values.add(val);

            if (node.left) queue.push([node.left, 2 * val + 1]);
            if (node.right) queue.push([node.right, 2 * val + 2]);
        }
    }

    find(target) {
        return this.values.has(target);
    }
}
```

---
# Intuition  
The given binary tree is "contaminated" with all values set to `-1`. However, we know the original tree follows a strict pattern:  
- The root node starts with `0`.  
- The left child of a node with value `x` has `2*x + 1`.  
- The right child of a node with value `x` has `2*x + 2`.  

Since this structure is **deterministic**, we can recover the tree using **Breadth-First Search (BFS)** or **Depth-First Search (DFS)** and store the values in a `set` or `hash table` for fast lookups.

---

# Approach  
1. **Use BFS to traverse the tree**:  
   - Start from the root (`0`).
   - Assign correct values to nodes based on their parent's value.  
   - Store each node's value in an **unordered set** (`O(1)` lookup time).  

2. **Use an unordered set (`values`)**:  
   - This allows us to check if a given number exists in **O(1) time**.

3. **For `find(target)`, simply check the set**:  
   - Since all possible values are precomputed, checking existence is **O(1)**.

---

# Complexity  
- **Time Complexity**:  
  - Tree recovery: **O(n)** (we visit each node once).  
  - Finding a target: **O(1)** (set lookup).  

- **Space Complexity**:  
  - **O(n)** (to store all values in the `unordered_set`).  


['Tree', 'Depth-First Search', 'Breadth-First Search', 'Binary Tree', 'Python', 'C++', 'Java', 'Python3', 'JavaScript']