Simple DFS Approach✅✅
Intuition:
The given binary tree is contaminated, meaning the values are incorrect.
The goal is to reconstruct the tree by following a rule where:
The root node

 # Intuition:
 * The given binary tree is contaminated, meaning the values are incorrect.
 * The goal is to reconstruct the tree by following a rule where:
    - The root node is assigned the `value 0`.
    - If a node has value x, then its left child is assigned `(2 * x + 1)` and right child is `(2 * x + 2)`.
 * Using `DFS`, we traverse the tree and restore the correct values.
 * A set is maintained to store all valid node values, allowing `O(1)` search for target values.
 # Approach:
  - Start `DFS traversal from the root`, assigning values to nodes using the given formula.
  - Store each value in an unordered_set for quick lookup.
  - Implement a `find` function that checks if a target value exists in the set.
 # Complexity:
  - Time Complexity: $$O(N)$$, where N is the number of nodes, as each node is visited once.
  - Space Complexity: $$O(N)$$, due to storing all node values in a set.
 
```cpp []
class FindElements {
public:
    TreeNode* newRoot;
    unordered_set<int> present;
    
    void dfs(TreeNode* root, int parentVal, bool left) {
        if (root == nullptr) return;
        
        root->val = left ? (2 * parentVal + 1) : (2 * parentVal + 2);
        present.insert(root->val);
        
        dfs(root->left, root->val, true);
        dfs(root->right, root->val, false);
    }
    
    FindElements(TreeNode* root) {
        root->val = 0;
        present.insert(0);
        dfs(root->left, 0, true);
        dfs(root->right, 0, false);
    }
    
    bool find(int target) {
        return present.count(target);
    }
};
```
```Python []
class FindElements:
    def __init__(self, root):
        self.present = set()
        root.val = 0
        self.present.add(0)
        self.dfs(root, 0, True)
        self.dfs(root, 0, False)

    def dfs(self, root, parentVal, left):
        if not root:
            return
        root.val = (2 * parentVal + 1) if left else (2 * parentVal + 2)
        self.present.add(root.val)
        self.dfs(root.left, root.val, True)
        self.dfs(root.right, root.val, False)

    def find(self, target):
        return target in self.present
```
```Java []
class FindElements {
    private Set<Integer> present = new HashSet<>();
    
    private void dfs(TreeNode root, int parentVal, boolean left) {
        if (root == null) return;
        
        root.val = left ? (2 * parentVal + 1) : (2 * parentVal + 2);
        present.add(root.val);
        
        dfs(root.left, root.val, true);
        dfs(root.right, root.val, false);
    }
    
    public FindElements(TreeNode root) {
        root.val = 0;
        present.add(0);
        dfs(root.left, 0, true);
        dfs(root.right, 0, false);
    }
    
    public boolean find(int target) {
        return present.contains(target);
    }
}
```
['Hash Table', 'Tree', 'Depth-First Search', 'Binary Tree', 'Python', 'C++', 'Java', 'Python3']