Find Elements in a Contaminated Binary Tree || Efficient 
IntuitionThe problem involves finding a value in a binary tree where all the nodes' values are initially set to be "corrupted" (e.g., some undefined or arbitrar
# Intuition
<!-- Describe your first thoughts on how to solve this problem. -->
The problem involves finding a value in a binary tree where all the nodes' values are initially set to be "corrupted" (e.g., some undefined or arbitrary values). We need to recover the values by using a specific rule based on their positions within the tree. The goal is to return whether a target value exists in the tree after it has been recovered using the rule.

The key insight is that each node's value can be determined by its position in the tree. The root node has a value of 0. For any given node, the value of its left child will be 2 * parent_value + 1 and the value of its right child will be 2 * parent_value + 2. Using this rule recursively, we can assign values to all nodes in the tree.
# Approach
<!-- Describe your approach to solving the problem. -->
**Tree Traversal:** We need to traverse the binary tree (we can use a depth-first search (DFS)) to assign values to each node using the given rule.
**Storing Values:** Since we want to be able to quickly check if a target value exists in the tree, we will store all the assigned values in a set (unordered_set). This allows us to efficiently check if a target value is present.
**Find Method:** Once the values are assigned, we can simply check if a given target value exists in the set.
# Steps:
- Initialize the root node's value to 0.
- Use a recursive function to assign values to the left and right children of each node according to the rule.
- Store all assigned values in an unordered set.
- Implement a method to check if a target value is present in the set.
# Complexity
# Time complexity:
<!-- Add your time complexity here, e.g. $$O(n)$$ -->
- Assigning values to all nodes requires a DFS traversal, which visits each node once. Hence, the time complexity is O(n), where n is the number of nodes in the tree.
- Checking if a target value exists in the set takes O(1) due to the constant time complexity of unordered_set lookup operations.
- Therefore, the overall time complexity is O(n) for the constructor and O(1) for the find method
# Space complexity:
<!-- Add your space complexity here, e.g. $$O(n)$$ -->
- The space complexity is O(n) due to the space required to store the values of the nodes in the set.
# 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 {
public:
    TreeNode* root;
    unordered_set<int> st;
    FindElements(TreeNode* root) {
        this->root=root;
        if(root) root->val = 0;
        st.insert(0);

        assign(root);
    }

    void assign(TreeNode* root){
        if(!root) return;

        if(root->left){
            root->left->val = 2*root->val+1;
            st.insert(root->left->val);
            assign(root->left);
        }

        if(root->right){
            root->right->val = 2*root->val+2;
            st.insert(root->right->val);
            assign(root->right);
        }
    }
    
    bool find(int target) {
        if(st.find(target)!=st.end()){
            return true;
        }
        return false;
    }
};

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