C# Solution for Find Elements In A Contaminated Binary Tree Problem
IntuitionThe problem involves a contaminated binary tree where all node values are initially -1, and we need to recover the original values using a fixed formul
# Intuition
<!-- Describe your first thoughts on how to solve this problem. -->
The problem involves a contaminated binary tree where all node values are initially -1, and we need to recover the original values using a fixed formula:
•	Left child: 2 * x + 1
•	Right child: 2 * x + 2

Since the tree follows a strict numerical pattern, we can recover all node values using a Depth-First Search (DFS) or Breadth-First Search (BFS) traversal. To efficiently check for the existence of a target value, we store all valid values in a HashSet, which provides O(1) lookup time.

# Approach
<!-- Describe your approach to solving the problem. -->
1.	Tree Recovery:
	•	Initialize a HashSet to store valid values.
	•	Start with root.val = 0 and use DFS (or BFS) to assign correct values to all nodes.
	•	Store each computed value in the HashSet for quick retrieval.
2.	Find Operation:
	•	Simply check if the target value exists in the HashSet using Contains(), which is an O(1) operation on average.

# Complexity
- Time complexity:
<!-- Add your time complexity here, e.g. $$O(n)$$ -->
1.	Tree Recovery (DFS/BFS):
	•	We visit each node once and compute its value in O(1) time.
	•	We insert n values into the HashSet in O(1) per operation.
	•	Overall Complexity: O(n)
2.	Find Operation:
	•	HashSet lookup takes O(1) on average.
	•	Overall Complexity: O(1) per query.

Thus, if we have q queries, the total time complexity is O(n + q).

- Space complexity:
<!-- Add your space complexity here, e.g. $$O(n)$$ -->
1.	Tree Recovery:
	•	The HashSet stores n values → O(n).
	•	The DFS recursive stack (or BFS queue) takes O(h) space, where h is the height of the tree (at most 20).
	•	Since O(h) ≤ O(n), the dominant factor is O(n).
2.	Find Operation:
	•	Uses only O(1) additional space.

Thus, the overall space complexity is O(n).

# Code
```csharp []
/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     public int val;
 *     public TreeNode left;
 *     public TreeNode right;
 *     public TreeNode(int val=0, TreeNode left=null, TreeNode right=null) {
 *         this.val = val;
 *         this.left = left;
 *         this.right = right;
 *     }
 * }
 */
public class FindElements {
    private HashSet<int> values;
    public FindElements(TreeNode root) {
        values = new HashSet<int>();
        RecoverTree(root, 0);
    }

    private void RecoverTree(TreeNode node, int value) {
        if (node == null) return;

        node.val = value;
        values.Add(value);
        
        RecoverTree(node.left, 2 * value + 1);
        RecoverTree(node.right, 2 * value + 2);
    }
    
    public bool Find(int target) {
        return values.Contains(target);
    }
}

/**
 * Your FindElements object will be instantiated and called as such:
 * FindElements obj = new FindElements(root);
 * bool param_1 = obj.Find(target);
 */
```
['C#']