JAVA Solution Using HashSet.
IntuitionThe problem involves reconstructing a contaminated binary tree where each node originally followed the rule:The root node starts with a value of 0.The
# Intuition
<!-- Describe your first thoughts on how to solve this problem. -->
The problem involves reconstructing a contaminated binary tree where each node originally followed the rule:

The root node starts with a value of 0.
The left child of a node with value x has a value of 2 * x + 1.
The right child of a node with value x has a value of 2 * x + 2.
Given a contaminated tree, we need to recover it using this rule and efficiently check if a target value exists in the tree.

# Approach
<!-- Describe your approach to solving the problem. -->
Recover the Tree:

Start at the root (val = 0).
Traverse the tree recursively using depth-first search (DFS).
Assign values to nodes based on the given rule.
Store all assigned values in a HashSet for quick lookup.
Find Operation:

Since we stored all recovered values in a HashSet, checking for a target value is an O(1) operation.

# Complexity
- Time complexity:
<!-- Add your time complexity here, e.g. $$O(n)$$ -->
Tree recovery: 
O(n), as we traverse each node once.

Find operation: 
O(1), since HashSet.contains() has average-case constant time complexity.

- Space complexity:
<!-- Add your space complexity here, e.g. $$O(n)$$ -->
O(n), as we store all node values in the HashSet.

# Code
```java []
/**
 * Definition for a binary tree node.
 * 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 {
    private HashSet<Integer> hs = new HashSet<>();

    private void solve(TreeNode root, int val, boolean left){
        if(root == null) return;
        root.val = left?(2*val + 1):(2*val + 2);
        hs.add(root.val);
        solve(root.left, root.val, true);
        solve(root.right, root.val, false);
    }

    public FindElements(TreeNode root) {
        root.val = 0;
        hs.add(0);
        solve(root.left, 0, true);
        solve(root.right, 0, false);
    }
    
    public boolean find(int target) {
        return hs.contains(target);
    }
}

/**
 * Your FindElements object will be instantiated and called as such:
 * FindElements obj = new FindElements(root);
 * boolean param_1 = obj.find(target);
 */
```
['Hash Table', 'Tree', 'Depth-First Search', 'Binary Tree', 'Java']