🌲 [🔥 Recover Contaminated Binary Tree | Fast & Clean C++/Python Solution] 💡 
IntroductionHey LeetCoders! 👋Today, we're tackling aninteresting tree problem—recovering a contaminated binary tree! The challenge here is to reconstruct a tree
# Introduction
Hey LeetCoders! 👋  
Today, we're tackling an **`interesting tree problem`**—recovering a contaminated binary tree! The challenge here is to reconstruct a tree that follows a **`specific mathematical pattern`** and then efficiently check if a given target exists.  

We'll be using **`DFS (Depth-First Search) + Hash Map`** to achieve an **`optimal`** solution in **`O(1) search time`**! 🚀  

---

# Problem Breakdown  
## Understanding the Contaminated Tree  
- The root always starts with `val = 0`.  
- Each node follows this rule:  
  - `left child = 2 * parent + 1`  
  - `right child = 2 * parent + 2`  
- But all values are initially set to `-1`, so we must **rebuild the tree** before searching.  

## Example Walkthrough 
### 🔹 Example 1:
```cpp
Input:  ["FindElements", "find", "find"]
        [[[-1,null,-1]], [1], [2]]
Output: [null, false, true]
```
#### Explanation:  
1. Recover tree → `{ 0, null, 2 }`  
2. `find(1) → false`, `find(2) → true`  

### 🔹 Example 2: 
```cpp
Input:  ["FindElements", "find", "find", "find"]
        [[[-1,-1,-1,-1,-1]], [1], [3], [5]]
Output: [null, true, true, false]
```
#### Explanation:  
###### Recovered tree → `{ 0, 1, 2, 3, 4 }`  
- `find(1) → true`  
- `find(3) → true`  
- `find(5) → false`  

---

# Approach - DFS + Hash Map for O(1) Search 
We need to **`recover the tree`** and efficiently **`check for any target value`**.  

✅ **Step 1: Recover the Tree Using DFS**  
- Start with `root->val = 0`.  
- Recursively assign values:  
  - `left = 2 * parent + 1`  
  - `right = 2 * parent + 2`  
- Store recovered values in an unordered_map (`O(1) lookup`).  

✅ Step 2: Fast Search in O(1) Time  
- The `find(target)` function simply checks if `target` exists in our hash map.  

---

# Time & Space Complexity  
## 📌 Time Complexity:  
- $$O(N)\ $$ for recovering the tree (DFS traversal).  
- $$O(1)\ $$ for `find(target)` (hash map lookup).  

## 📌 Space Complexity:  
- $$O(N)\ $$ for storing values in the hash map.  

---
![c1ee5054-dd07-4caa-a7df-e21647cfae9e_1709942227.5165014.png](https://assets.leetcode.com/users/images/55e4c5e3-5225-463f-92bf-fbe15792bf19_1740097677.7868047.png)


# C++ Solution - DFS + Hash Map | Python Solution - DFS + Hash Set
```cpp []
class FindElements {
public:
    unordered_map<int, bool> mp;

    void recover(TreeNode* root) {
        if (root->left) {
            root->left->val = root->val * 2 + 1;
            mp[root->left->val] = true;
            recover(root->left);
        }
        if (root->right) {
            root->right->val = root->val * 2 + 2;
            mp[root->right->val] = true;
            recover(root->right);
        }
    }

    FindElements(TreeNode* root) {
        root->val = 0;
        mp[0] = true;
        recover(root);
    }
    
    bool find(int target) {
        return mp[target];
    }
};
```

```python []
class FindElements:
    def __init__(self, root: TreeNode):
        self.values = set()
        
        def recover(node, val):
            if not node:
                return
            node.val = val
            self.values.add(val)
            recover(node.left, 2 * val + 1)
            recover(node.right, 2 * val + 2)
        
        recover(root, 0)
    
    def find(self, target: int) -> bool:
        return target in self.values
```

---

# Step-by-Step Execution for `find(3)`  
Let’s say we have the following **contaminated tree**:  
```
       -1
      /   \
    -1     -1
   /  \
 -1   -1
```
## Recovery Process (DFS Traversal)
| Node | Recovered Value |
|------|----------------|
| root | 0 |
| root->left | 1 |
| root->right | 2 |
| root->left->left | 3 |
| root->left->right | 4 |

Final Tree (after recovery):  
```
       0
      / \
     1   2
    / \
   3   4
```
Now, when we call `find(3)`, we simply **check our hash map**:  
✅ **Exists → return true!**  

---

# **Conclusion**  
This approach ensures a **fast recovery** and **instant lookups**. 🔥  

💬 **Did this help?** Let me know in the comments! And if you liked it, **drop an upvote 🔼 to support more high-quality solutions! 🚀**

---

![1HBC0324_COV.jpg](https://assets.leetcode.com/users/images/412c56e7-94ef-4bf2-a56d-48a5d59585ae_1740097830.0858788.jpeg)

['Hash Table', 'Tree', 'Depth-First Search', 'Design', 'Binary Tree', 'Ordered Set', 'C++', 'Python3']