Easy to understand and Easy Approach(Beat 80%) 😊😊
IntuitionThe problem is about reconstructing a contaminated binary tree where all values are initially set to -1. We are given the root node of this tree, and w
# Intuition
<!-- Describe your first thoughts on how to solve this problem. -->
The problem is about reconstructing a contaminated binary tree where all values are initially set to -1. We are given the root node of this tree, and we need to recover the original values following a specific rule:

* The root node is assigned the value 0.
* For a node with value x:
--> Its left child gets the value 2*x + 1.
--> Its right child gets the value 2*x + 2.

After reconstructing the tree, we must support find(target), which checks whether a given target value exists in the tree efficiently.

# Approach
<!-- Describe your approach to solving the problem. -->
1. Reconstruct the tree using DFS (Depth-First Search)

* Start from the root with an initial value of 0.
* Use DFS to traverse and assign values to the nodes based on the given formula.
* Store these values in a Set<Integer> (hash set) to allow O(1) lookup.
2. Check for presence using HashSet

* Since all valid node values are stored in a Set, checking whether a target value exists is an O(1) operation.

# Complexity
- Time complexity:
<!-- Add your time complexity here, e.g. $$O(n)$$ -->

- Space complexity:
<!-- Add your space complexity here, e.g. $$O(n)$$ -->

# Code- 1 (Based on HashSet)
```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 {

    Set<Integer> op;

        public FindElements(TreeNode root) {
            op = new HashSet<>();
            maker(root, 0);
        }
        public void maker(TreeNode root, int val){
            if(root == null){
                return;
            }
            op.add(val);
            maker(root.left, 2*val+1);
            maker(root.right, 2*val+2);
        }

        public boolean find(int target) {
            return op.contains(target);
        }
}

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

# Code- 2 (Based on Tree)
```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 {

    TreeNode cont;

        public FindElements(TreeNode root) {
            cont = maker(root, 0);

        }
        public TreeNode maker(TreeNode root, int val){
            if(root == null){
                return null;
            }
            TreeNode node = new TreeNode(val);
            node.left = maker(root.left, 2*val+1);
            node.right = maker(root.right, 2*val+2);
            return node;
        }

        public boolean find(int target) {
            return finder(cont, target);
        }
        public boolean finder(TreeNode cont, int tar){
            if(cont == null){
                return false;
            }
            if(cont.val == tar){
                return true;
            }
            return finder(cont.left, tar) || finder(cont.right, tar);
        }
}
['Hash Table', 'Tree', 'Depth-First Search', 'Design', 'Binary Tree', 'Java']