🔥BEATS 💯 % 🎯 |✨SUPER EASY BEGINNERS 👏| JAVA | C | C++ | PYTHON| JAVASCRIPT | DART 
🚀 IntuitionThe problem gives us acontaminated binary tree, where each node's value is corrupted.We need torecover the treeby following these rules:
The root is
![image.png](https://assets.leetcode.com/users/images/2cfd20ee-576a-45b2-9887-4b7f5f35afc8_1740119996.1221058.png)

---



## **🚀 Intuition**  
The problem gives us a **contaminated binary tree**, where each node's value is corrupted.  
We need to **recover the tree** by following these rules:  
1. The root is set to `0`.  
2. If a node has value `x`:  
   - The left child gets value `2x + 1`.  
   - The right child gets value `2x + 2`.  

Once recovered, we should **check if a given target exists** in the tree efficiently.  

---

## **💡 Approach**  
### **🔹 Steps to Solve 🔹**  
1. **Recover the tree** during initialization using **DFS**.  
2. **Store all node values** in a **set or list** for quick lookup.  
3. **Check for a target value** using `contains()` (for efficient searching).  

---

## **📝 Complexity Analysis**  
- **Time Complexity:**  
  - **O(n)** → We traverse `n` nodes to recover the tree.  
  - **O(1)** → Checking if a number exists is **O(1)** for a **set** and **O(n)** for a **list**.  
- **Space Complexity:**  
  - **O(n)** → We store all `n` values in a list or set.  

---


```dart []
/**
 * Definition for a binary tree node.
 * class TreeNode {
 *   int val;
 *   TreeNode? left;
 *   TreeNode? right;
 *   TreeNode([this.val = 0, this.left, this.right]);
 * }
 */
class FindElements {
  List<int> elements = [];

  FindElements(TreeNode? root) {
    _helper(root, 0);
  }
  
  void _helper(TreeNode? node, int val) {
    if (node == null) return;
    node.val = val;
    elements.add(val);
    _helper(node.left, val * 2 + 1);
    _helper(node.right, val * 2 + 2);
  }

  bool find(int target) => elements.contains(target);
}

/**
 * Your FindElements object will be instantiated and called as such:
 * FindElements obj = FindElements(root);
 * bool param1 = obj.find(target);
 */
```


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

class TreeNode {
    int val;
    TreeNode left, right;
    TreeNode(int x) { val = x; }
}

class FindElements {
    Set<Integer> elements = new HashSet<>();

    public FindElements(TreeNode root) {
        recover(root, 0);
    }

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

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


```python []
class TreeNode:
    def __init__(self, x):
        self.val = x
        self.left = None
        self.right = None

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

    def find(self, target: int) -> bool:
        return target in self.elements
```


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

struct TreeNode {
    int val;
    TreeNode* left;
    TreeNode* right;
    TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
};

class FindElements {
private:
    unordered_set<int> elements;

    void recover(TreeNode* node, int val) {
        if (!node) return;
        node->val = val;
        elements.insert(val);
        recover(node->left, val * 2 + 1);
        recover(node->right, val * 2 + 2);
    }

public:
    FindElements(TreeNode* root) {
        recover(root, 0);
    }

    bool find(int target) {
        return elements.find(target) != elements.end();
    }
};
```


```javascript []
class TreeNode {
    constructor(val = 0, left = null, right = null) {
        this.val = val;
        this.left = left;
        this.right = right;
    }
}

class FindElements {
    constructor(root) {
        this.elements = new Set();
        this.recover(root, 0);
    }

    recover(node, val) {
        if (!node) return;
        node.val = val;
        this.elements.add(val);
        this.recover(node.left, val * 2 + 1);
        this.recover(node.right, val * 2 + 2);
    }

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

---

## **✨ Summary Table**
| Language   | Time Complexity | Space Complexity |
|------------|---------------|----------------|
| **Dart**   | **O(n)** | **O(n)** |
| **Java**   | **O(n)** | **O(n)** |
| **Python** | **O(n)** | **O(n)** |
| **C++**    | **O(n)** | **O(n)** |
| **JS**     | **O(n)** | **O(n)** |

---

# **🔥 Why This Solution is the Best?**  
✅ **Beats 100% in Speed** → Efficient `O(n)` recovery and `O(1)` lookup.  
✅ **DFS for Recovery** → Simple and fast tree traversal.  
✅ **Optimized Data Structures** → `Set` for `O(1)` lookups.  

🚀 **Hope this helps! Happy Coding!** 🚀

---

![image.png](https://assets.leetcode.com/users/images/d81a7cee-fa73-41a2-82dc-65bf475d960c_1722267693.3902693.png) {:style='width:250px'}
['Tree', 'Depth-First Search', 'C', 'Binary Tree', 'C++', 'Java', 'Python3', 'JavaScript', 'Dart', 'Python ML']