Most intuitive solution, Easy understanding. Beats 100%😎😎🔥🔥
IntuitionThe problem states that the binary tree has been "contaminated," meaning all values are -1. However, we are given a specific set of transformation rule
# Intuition
The problem states that the binary tree has been "contaminated," meaning all values are -`1`. However, we are given a specific set of transformation rules that determine the correct values for each node based on its parent.

- Since the root is `0`, we can reconstruct the entire tree using **DFS (Depth-First Search)** or **BFS (Breadth-First Search)**.
- Once reconstructed, checking for the existence of any `target` value should be efficient. Using an unordered_set helps in achieving constant-time lookups.

# Approach
1. Recover the tree using DFS:

    - Start from the root and assign `0` as its value.
    - Recursively traverse the left and right children:
        - Left child gets `2 * parent + 1`
        - Right child gets `2 * parent + 2`
    - Store all recovered values in an unordered_set for quick lookups.
2. Find function:

    - Simply check if the target value exists in the unordered_set using `count(target)`, which takes **O(1)** on average.


# Complexity
- Time complexity:
    - **O(n)**  
    for recovering the tree (traversing each node once).
    - **O(1)** 
    for checking existence in the `unordered_set`.
    - Total: **O(n)**

- Space complexity:
    - **O(n)** 
    for storing the node values in an `unordered_set`.
    - **O(n)** 
    worst-case recursion depth (for a skewed tree).
    - Total: **O(n)**

# Code
```cpp []
/**
 * Definition for a binary tree node.
 * 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> st;
    void vaccinate(TreeNode* root, int value){
        // base case -> when root is not present
        if(!root) return ;

        root->val = value;
        st.insert(value);
        vaccinate(root->left, 2*value + 1);
        vaccinate(root->right, 2*value + 2);
    }
public:
    FindElements(TreeNode* root) {
        vaccinate(root, 0);
    }
    
    bool find(int target) {
        return st.count(target);
    }
};

/**
 * Your FindElements object will be instantiated and called as such:
 * FindElements* obj = new FindElements(root);
 * bool param_1 = obj->find(target);
 */
```

![Untitled design (2).png](https://assets.leetcode.com/users/images/64906572-1c81-4de4-9efa-e3b1ea98141d_1740115736.819999.png)

['Hash Table', 'Tree', 'Depth-First Search', 'Breadth-First Search', 'Design', 'Binary Tree', 'C++']