✅💯 % ON RUNTIME | 😁EASY SOLUTION | 😎PROPER EXPLANATION
Here’s a well-structured and detailed version of your solution explanation:🧠 IntuitionWhen given a contaminated binary tree where every node's value is set to-1
Here’s a well-structured and detailed version of your solution explanation:  

---

# 🧠 Intuition  
When given a contaminated binary tree where every node's value is set to `-1`, our goal is to recover it based on certain rules:  
- The root node's value is set to `0`.  
- The left child of a node with value `x` has a value of `2*x + 1`.  
- The right child of a node with value `x` has a value of `2*x + 2`.  

After recovering the tree, we need to check if a given value exists in it efficiently. Since the tree follows a specific pattern, we can store all values in a **HashSet** for quick lookup (O(1) time complexity).  

---

# 🏗️ Approach  
### 🔹 Step 1: Initialize the Data Structure  
- Create a **HashSet** to store all recovered values.  
- Use a helper function to traverse and restore the tree recursively.  

### 🔹 Step 2: Recover the Tree (`newTree` function)  
- Start from the root and assign it the value `0`.  
- If a node exists:  
  - Compute the left child’s value as `2 * value + 1` and recurse on it.  
  - Compute the right child’s value as `2 * value + 2` and recurse on it.  
- Store each node’s value in the **HashSet**.  

### 🔹 Step 3: Implement the `find` function  
- Simply check if the **target value exists in the HashSet**.  

### 📌 Example  
Consider the contaminated tree:  
```
        -1
       /   \
     -1    -1
    /  \   /  \
  -1   -1 -1  -1
```
After recovering, it becomes:  
```
        0
       /   \
      1     2
     / \   /  \
    3   4 5    6
```
- If `find(4)` is called, return `true` ✅  
- If `find(10)` is called, return `false` ❌  

---

# ⏳ Complexity Analysis  
- **Time Complexity**  
  - `newTree` function: **O(n)** (as we traverse all nodes once).  
  - `find` function: **O(1)** (since HashSet lookup is constant time).  
- **Space Complexity**  
  - **O(n)** (as we store all node values in a HashSet).  

---

# 💻 Code  

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

class FindElements {
    HashSet<Integer> set; // Stores all recovered values

    public FindElements(TreeNode root) {
        set = new HashSet<>();
        recoverTree(root, 0);
    }
    
    public boolean find(int target) {
        return set.contains(target);
    }

    private void recoverTree(TreeNode root, int value) {
        if (root == null) return;
        set.add(value);
        root.val = value;
        recoverTree(root.left, 2 * value + 1);
        recoverTree(root.right, 2 * value + 2);
    }
}
```

```python []
class FindElements:
    def __init__(self, root):
        self.values = set()
        self.recover_tree(root, 0)

    def recover_tree(self, node, value):
        if not node:
            return
        self.values.add(value)
        node.val = value
        self.recover_tree(node.left, 2 * value + 1)
        self.recover_tree(node.right, 2 * value + 2)

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

```cpp []
#include <unordered_set>
using namespace std;

class FindElements {
private:
    unordered_set<int> values;

    void recoverTree(TreeNode* root, int value) {
        if (!root) return;
        root->val = value;
        values.insert(value);
        recoverTree(root->left, 2 * value + 1);
        recoverTree(root->right, 2 * value + 2);
    }

public:
    FindElements(TreeNode* root) {
        recoverTree(root, 0);
    }
    
    bool find(int target) {
        return values.count(target);
    }
};
```
``` javascript []
class TreeNode {
    int val;
    TreeNode left;
    TreeNode right;

    TreeNode() {}

    TreeNode(int val) {
        this.val = val;
    }

    TreeNode(int val, TreeNode left, TreeNode right) {
        this.val = val;
        this.left = left;
        this.right = right;
    }
}

class FindElements {
    private HashSet<Integer> values;

    public FindElements(TreeNode root) {
        values = new HashSet<>();
        recoverTree(root, 0);
    }

    private void recoverTree(TreeNode node, int value) {
        if (node == null) return;
        node.val = value;
        values.add(value);
        recoverTree(node.left, 2 * value + 1);
        recoverTree(node.right, 2 * value + 2);
    }

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

/**
 * Your FindElements object will be instantiated and called as such:
 * FindElements obj = new FindElements(root);
 * boolean param_1 = obj.find(target);
 */


```
```typescript []
class FindElements {
    private values: Set<number>;

    constructor(root: TreeNode | null) {
        this.values = new Set<number>();
        this.recoverTree(root, 0);
    }

    private recoverTree(node: TreeNode | null, value: number): void {
        if (!node) return;
        node.val = value;
        this.values.add(value);
        this.recoverTree(node.left, 2 * value + 1);
        this.recoverTree(node.right, 2 * value + 2);
    }

    find(target: number): boolean {
        return this.values.has(target);
    }
}

```

# 🎯 Final Thoughts  
✅ **Key Takeaways:**  
- Used **DFS (Depth-First Search)** to reconstruct the tree.  
- Stored values in a **HashSet** for fast lookup.  
- Achieved **O(n) construction** and **O(1) search time complexity**.  

🚀 This approach ensures an efficient solution that works well even for large trees!😊

![upvote image.jpg](https://assets.leetcode.com/users/images/5c7f1b54-667b-4559-bfa1-6b12406d290d_1740099626.5112574.jpeg)


['Hash Table', 'Tree', 'Recursion', 'Python', 'Java', 'Python3', 'JavaScript', 'C#']