"⚡ Fast Java & C++Solution to Recover Binary Tree & Efficient Find Operation 🌳"| DFS Approach
IntuitionThe problem asks us to recover a binary tree where some of the nodes may have corrupted values (i.e., they are initially set to -1). We're given that t
# Intuition
<!-- Describe your first thoughts on how to solve this problem. -->
The problem asks us to recover a binary tree where some of the nodes may have corrupted values (i.e., they are initially set to -1). We're given that the tree's structure is still intact, and the root value should be 0. The values of the other nodes in the tree can be restored using the properties of a complete binary tree.

A complete binary tree's node values can be restored by using the following observation:

For any node with value x:
The left child should have a value of 2 * x + 1.
The right child should have a value of 2 * x + 2.
Given this, we need to traverse the tree and restore the values using DFS or BFS. We also need to be able to efficiently check if a given value exists in the tree.

# Approach
<!-- Describe your approach to solving the problem. -->
We can approach this problem in two phases:

Tree Recovery Phase (DFS):

Start from the root node and set its value to 0.
Use a recursive function (rec()) to traverse the tree. For each node, we set its value and recurse on its left and right children, calculating their values using the formula 2 * parent_value + 1 for the left child and 2 * parent_value + 2 for the right child.
Find Operation:

Store all the node values in a HashSet while performing the recovery so that we can quickly check if a target value exists in the tree.
The main idea is that we can use DFS to both recover the tree and populate the HashSet for efficient lookup.

# Complexity
- Time complexity:
<!-- Add your time complexity here, e.g. $$O(n)$$ -->
𝑂(𝑛)
We visit each node exactly once during the DFS traversal, where n is the number of nodes in the tree. The time complexity for the find operation is 𝑂(1) because of the HashSet lookup.

- Space complexity:
<!-- Add your space complexity here, e.g. $$O(n)$$ -->
O(n)
The space complexity is determined by the recursion stack used during the DFS and the space used by the HashSet to store the node values. Since we store values for each node in the tree and the recursion depth is at most n, the space complexity is 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 {
    TreeNode root;
    HashSet<Integer> h;
    public FindElements(TreeNode root) {
        //root.val = 0;
        h = new HashSet<>();
        root = rec(root , 0);
        //root = rec(root.left , 0);
        this.root = root;
    }
    
    public boolean find(int target) {
        return h.contains(target);
    }
    private TreeNode rec(TreeNode root, int val)
    {
        if(root == null)
            return root;
        root.val = val;
        h.add(val);
        root.right = rec(root.right , 2 * val + 2);
        root.left = rec(root.left , 2 * val + 1);
        return root;
    }
}
/**
 * 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 {
public:
    unordered_set<int> h;
    
    // Constructor to initialize the tree and recover its values
    FindElements(TreeNode* root) {
        recoverTree(root, 0);
    }
    
    // Function to find if the target value exists in the tree
    bool find(int target) {
        return h.find(target) != h.end();
    }

private:
    // Helper function to recursively recover the tree's node values
    void recoverTree(TreeNode* root, int val) {
        if (root == nullptr)
            return;

        root->val = val;           // Set the node value
        h.insert(val);             // Store the value in the hash set
        
        // Recur on left and right children, updating their values
        recoverTree(root->left, 2 * val + 1);   // Left child value: 2 * parent_value + 1
        recoverTree(root->right, 2 * val + 2);  // Right child value: 2 * parent_value + 2
    }
};

/**
 * Your FindElements object will be instantiated and called as such:
 * FindElements* obj = new FindElements(root);
 * bool param_1 = obj->find(target);
 */

['C++', 'Java']