✅ Beats 100% 🔥||🧑‍💻 BEGINNER FREINDLY||🌟JAVA||C++
IntuitionApproach1.Recover a contaminated binary tree (all nodes = -1) to its original state:. Root value = 0.
. Left child of x = 2 * x + 1.
. Right child of x
# Intuition
<!-- Describe your first thoughts on how to solve this problem. -->

# Approach
<!-- Describe your approach to solving the problem. -->
1.Recover a contaminated binary tree (all nodes = ```-1```) to its original state:

. Root value = ```0```.
. Left child of ```x``` = ```2 * x + 1```.
. Right child of ```x``` = ```2 * x + 2```.

Implement a ```find``` method to check if a target value exists in the recovered tree.

**2. Solution**
. Use  **DFS** to recover the tree:
. Start from the root with value ```0```.
. For each node, compute left child (```2 * x + 1```) and right child (```2 * x + 2```).
. Store all recovered values in a ```HashSet``` for O(1) lookups.

**Find Method:**
. Check if the target exists in the HashSet.

_____
# Complexity
- Time complexity:**O(N)**
<!-- Add your time complexity here, e.g. $$O(n)$$ -->

- Space complexity:**O(N)** for HashSet and recursion stack.
<!-- Add your space complexity here, e.g. $$O(n)$$ -->
___
### Solution Steps with Diagram:
**Step 1: Contaminated Tree**
All nodes are initialized to ```-1```.
```[]   
        -1
       /   \
     -1     -1

```
_____
**Step 2: Recover the Tree Using DFS**
Start from the root with value ```0```.

1.**Recover Root:**
.Assign ```0``` to the root.
.Add ```0``` to the ```HashSet```.
```[]
        0
       /   \
     -1     -1
```
HashSet: ```{0}```
_______________
**2.Recover Left Child of Root:**
.Value = ```2 * 0 + 1 = 1```.
.Assign ```1``` to the left child.
.Add ```1``` to the ```HashSet```.
```[]
        0
       /   \
      1     -1
```
**HashSet:** ```{0, 1}```.
_____
**3.Recover Right Child of Root:**
.Value = ```2 * 0 + 2 = 2```.
.Assign ```2``` to the right child.
.Add ```2``` to the HashSet.
```[]
        0
       /   \
      1     2
```
**HashSet:** ```{0, 1, 2}```
_____
**Step 3: Final Recovered Tree**
The tree is now fully recovered with correct values.
```[]
         0
       /   \
      1     2
```
**HashSet:** ```{0, 1, 2}```
**Step 4: Find Method**
  .Check if a target value exists in the ```HashSet```.
**Example 1:** ```find(1)```
  .```1``` is in the ```HashSet``` → Return ```true```.
**Example 2:** ```find(3)```
.```3``` is not in the ```HashSet``` → Return ```false```.
___

### Color-Coded Diagram

**Contaminated Tree**
```[]
        🔴-1
       /     \
     🔴-1    🔴-1
```
**Recovered Tree**
```[]
        🟢0
       /     \
     🟢1     🟢2
```
**HashSet**
```[]
{🟢0, 🟢1, 🟢2}
```

# Code
```java []
class FindElements {
    private Set<Integer> recoveredValues;

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

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

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

```c++ []
class TreeNode {
public:
    int val;
    TreeNode *left;
    TreeNode *right;
    
    TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
};

class FindElements {
private:
    std::unordered_set<int> recoveredValues;

    void recoverTree(TreeNode* node, int value) {
        if (node == nullptr) {
            return;
        }
        node->val = value;
        recoveredValues.insert(value);
        recoverTree(node->left, 2 * value + 1); // Recover left child
        recoverTree(node->right, 2 * value + 2); // Recover right child
    }

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

    bool find(int target) {
        return recoveredValues.find(target) != recoveredValues.end();
    }
};
```
**If you found my solution helpful, I would greatly appreciate your upvote, as it would motivate me to continue sharing more solutions😊**.








['Hash Table', 'Tree', 'Depth-First Search', 'C++', 'Java']