🔥 Beats 98.92% 🔥 | 🌟 Proof 🌟 | ✔️ Detailed Explaination ✔️ | HashSet + DFS | 2 Solution
IntuitionThe problem requires us to recover acontaminated binary treewhere all node values are initially-1. Werestore the tree using a simple formula: the root
---
![image.png](https://assets.leetcode.com/users/images/6d10b17c-26de-45dc-b7b4-aa9c76222b17_1740108057.6060863.png)

---

# Intuition
The problem requires us to recover a **contaminated binary tree** where all node values are initially `-1`. We **restore the tree using a simple formula**: the root is assigned `0`, the left child is `2 * parent + 1`, and the right child is `2 * parent + 2`. To efficiently support the `find(target)` operation, we store all **recovered values** in a `HashSet`, allowing ``O(1)`` lookup time. We use `DFS`  to traverse and restore the **tree**, ensuring all values are correctly assigned. 

# Approach
`Step 1` **Recover the Tree**
- Start from the `root`, assign `0` to **its value**.
- Use `DFS` to assign values to the `left` and `right` children:
    - Left `leftChild = 2 * parent + 1`
    - Right `rightChild = 2 * parent + 2`
- Store each recovered value in a HashSet for quick lookups.

`Step 2` **Implement the find() function**
- Simply **check** if the `target` exists in the `HashSet`.
- If found, return `true`, else return `false`.

# Complexity
- Time complexity : $$O(n) + O(1)$$
- Space complexity : $$O(n)$$

# 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 Set<Integer> values = new HashSet<>();

    // Step 1: Recover the tree using DFS
    private void recover(TreeNode node, int val)
    {
        if (node == null)
        {
            return;
        } 

        node.val = val;
        values.add(val);
        recover(node.left, 2 * val + 1);
        recover(node.right, 2 * val + 2);
    }

    // Step 2: Constructor to recover tree
    public FindElements(TreeNode root)
    {
        recover(root, 0);
    }

    // Step 3: Find function (O(1) lookup)
    public boolean find(int target)
    {
        return values.contains(target);
    }
}

/**
 * Your FindElements object will be instantiated and called as such:
 * FindElements obj = new FindElements(root);
 * boolean param_1 = obj.find(target);
 */
```
``` C++ []
/**
 * 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
{
private:
    unordered_set<int> values;

    // Step 1: Recover the tree using DFS
    void recover(TreeNode* node, int val)
    {
        if (!node)
        {
            return;
        } 
        
        node->val = val;
        values.insert(val);
        recover(node->left, 2 * val + 1);
        recover(node->right, 2 * val + 2);
    }

public:
    // Step 2: Constructor to recover tree
    FindElements(TreeNode* root)
    {
        recover(root, 0);
    }

    // Step 3: Find function (O(1) lookup)
    bool find(int target)
    {
        return values.find(target) != values.end();
    }
};


/**
 * Your FindElements object will be instantiated and called as such:
 * FindElements* obj = new FindElements(root);
 * bool param_1 = obj->find(target);
 */
```
['Array', 'Hash Table', 'String', 'Tree', 'Depth-First Search', 'Breadth-First Search', 'Recursion', 'Binary Tree', 'C++', 'Java']