✅ Easy to Understand | Beginner Friendly | Tree | Design | Hash Table | Detailed Video Explanation🔥
IntuitionThe problem involves reconstructing a contaminated binary tree where all values were replaced with-1. Given a root node, we need to recover the tree fo
# Intuition
The problem involves reconstructing a contaminated binary tree where all values were replaced with `-1`. Given a root node, we need to recover the tree following a specific formula:
- The root node is assigned a value of `0`.
- The left child of a node with value `val` is assigned `2 * val + 1`.
- The right child is assigned `2 * val + 2`.

To efficiently check if a given target value exists in the tree, we can store all valid node values in a `HashSet` during the reconstruction.

# Approach
1. **Use Depth-First Search (DFS)** to traverse the tree and recover node values:
   - Start from the root and assign it `0`.
   - Recursively assign values to the left and right children using the given formula.
   - Store each assigned value in a `HashSet` for quick lookup.
2. **Implement a `find()` function** that checks if a given target exists in the set.
3. The solution ensures efficient retrieval since checking existence in a `HashSet` takes `O(1)` time on average.

# Complexity
- **Time complexity:**  
  - Constructing the tree involves visiting each node once → $$O(n)$$
  - Checking for a value in the `HashSet` is $$O(1)$$ on average.
  - Overall, the time complexity is **$$O(n)$$**.

- **Space complexity:**  
  - We store all `n` recovered node values in a `HashSet` → **$$O(n)$$**.
  - Recursive DFS calls take **$$O(h)$$** space (where `h` is the tree height).  
  - In a skewed tree, `h = n`, but in a balanced tree, `h = log(n)`.  
  - Worst case: **$$O(n)$$**, Best case: **$$O(log n)$$**.


# Code
```java []
class FindElements {
    Set<Integer> set; // Stores the values of the recovered tree

    // Constructor to reconstruct the tree and populate the set
    public FindElements(TreeNode root) {
        set = new HashSet<>();
        sol(root, 0); // Start the recovery process with the root having value 0
    }

    // Method to check if a target value exists in the reconstructed tree
    public boolean find(int target) {
        return set.contains(target);
    }

    // Recursive helper function to recover the tree values
    private void sol(TreeNode root, int val) {
        if (root == null) return; // Base case: If node is null, return

        root.val = val; // Assign the correct value to the current node
        set.add(val); // Add the value to the set

        // Recursively assign values to the left and right children
        sol(root.left, 2 * val + 1);
        sol(root.right, 2 * val + 2);
    }
}

```

https://youtu.be/rLRrNVsOZjc


['Hash Table', 'Tree', 'Depth-First Search', 'Design', 'Binary Tree', 'Java']