🔥Beats 100% | Easy for Beginners | ✨ 2 Approaches | Java | C++ 
IntuitionAn Contaminated binary tree is given, where each node value is corrupted. We need to recover the tree by following conditions ->
The root node value is

![Screenshot 2025-02-21 194327.png](https://assets.leetcode.com/users/images/72663326-eb0d-4f8b-bcb3-f841983135e1_1740153257.2949255.png)


# Intuition
An Contaminated binary tree is given, where each node value is corrupted. We need to recover the tree by following conditions ->
1. The root node value is set to `0`.
2. If a node has value `x`:
    - The left child value is `2 * x + 1`.
    - The right child value is `2 * x + 2`.

****

# Approach 1 <=> Using Set
1. Recover the tree using Depth First Search.
2. Store the values in the set.
3. Check for the value in the set when `find()` is called.

****

# Complexity
- **Time complexity:**
    - **O(N)**: For traversing `n` nodes to recover the node values.
    - **O(1)**: Checking if the number exists in the set or not.

- **Space complexity:**
    - **O(N)**: For storing the values in the set.

****

# Code
```cpp []
struct TreeNode {
    int val;
    TreeNode *left;
    TreeNode *right;
    TreeNode() : val(0), left(nullptr), right(nullptr) {}
    TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
    TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}
};

class FindElements {
private:
    unordered_set<int> s;

    void recover(TreeNode* root, int data){
        if(root == NULL){
            return;
        }

        root -> val = data;
        s.insert(data);

        recover(root -> right, 2 * data + 2);
        recover(root -> left, 2 * data + 1);
    }

public:
    FindElements(TreeNode* root) {
        recover(root, 0);
    }
    
    bool find(int target) {
        if(s.find(target) != s.end()){
            return true;
        }

        return false;
    }
};
```
```java []
public 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 {
    HashSet<Integer> s;

    void recover(TreeNode node, int data){
        if(node == null){
            return;
        }

        node.val = data;
        s.add(data);

        recover(node.right, 2 * data + 2);
        recover(node.left, 2 * data + 1);
    }

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

****

# Approach 2 <=> Using Map
1. Recover the tree using Depth First Search.
2. Store the values in the map.
3. Check for the value in the map when `find()` is called.

****

# Complexity
- **Time complexity:**
    - **O(N)**: For traversing `n` nodes to recover the node values.
    - **O(1)**: Checking if the number exists in the map or not.

- **Space complexity:**
    - **O(N)**: For storing the values in the map.

****

# Code
```cpp []
struct TreeNode {
    int val;
    TreeNode *left;
    TreeNode *right;
    TreeNode() : val(0), left(nullptr), right(nullptr) {}
    TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
    TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}
};

class FindElements {
private:
    unordered_map<int, int> mp;

    void recover(TreeNode* root, int data){
        if(root == NULL){
            return;
        }

        root -> val = data;
        mp[data]++;

        recover(root -> right, 2 * data + 2);
        recover(root -> left, 2 * data + 1);
    }

public:
    FindElements(TreeNode* root) {
        recover(root, 0);
    }
    
    bool find(int target) {
        if(mp.find(target) != mp.end()){
            return true;
        }

        return false;
    }
};

```
```java []

public 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 {
    HashMap<Integer, Integer> mp;

    void recover(TreeNode node, int data){
        if(node == null){
            return;
        }

        node.val = data;
        mp.put(data, 1);

        recover(node.right, 2 * data + 2);
        recover(node.left, 2 * data + 1);
    }

    public FindElements(TreeNode root) {
        mp = new HashMap<>();
        recover(root, 0);
    }
    
    public boolean find(int target) {
        return mp.containsKey(target);
    }
}

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