Super Simple Approch✅ 🚀 | Step-By-Step Explained 🔥 | C++ | Java | Python | Js
🔍 IntuitionThe given binary tree is contaminated, meaning its values are not reliable. However, we know the rule for reconstructing it:
🌱 The root is always0.
🌿
# 🔍 Intuition  
The given binary tree is contaminated, meaning its values are not reliable. However, we know the rule for reconstructing it:  
- 🌱 The root is always `0`.  
- 🌿 The left child of a node with value `x` is `2 * x + 1`.  
- 🌳 The right child of a node with value `x` is `2 * x + 2`.  

Using this rule, we can recover the entire tree. Additionally, we need to efficiently check if a given `target` value exists in the recovered tree.  

# 🛠️ Approach  
1. **Tree Reconstruction:**  
   - Start from the given `root` and set its value to `0`.  
   - Perform a **DFS (Depth-First Search) 🔎** to traverse the tree.  
   - Assign values to the left and right children using the formulas:  
     - Left child: `2 * x + 1`  
     - Right child: `2 * x + 2`  
   - Store all recovered values in a `vector`.  

2. **Find Operation:**  
   - Check if the `target` exists in the stored values.  
   - ✅ Use a **linear search** (`O(n)`) to find the target in the `vector`.  

# ⏳ Complexity  
- **Time Complexity:**  
  - Tree reconstruction takes **O(n) ⏱️** since each node is visited once.  
  - Searching in a `vector` takes **O(n) 🧐** in the worst case.  
  - **Overall:** **O(n) 🌀**  

- **Space Complexity:**  
  - We store all node values, requiring **O(n) 📦** additional space.  
  - **Overall:** **O(n) 📊**  

# Code
```cpp []
class FindElements {
public:
    /**
     * Recursively restores the values of the tree nodes.
     * - The root starts with value `0`.
     * - The left child of a node with value `x` is assigned `2 * x + 1`.
     * - The right child of a node with value `x` is assigned `2 * x + 2`.
     */
    void solve(TreeNode* root) {
        if (root == NULL) {
            return;  // Base case: If the node is NULL, stop the recursion
        }

        // Store the restored value in the list
        values_list.push_back(root->val);

        // Process left child (if exists)
        if (root->left != NULL) {
            root->left->val = root->val * 2 + 1;  // Assign new value
        }
        solve(root->left);

        // Process right child (if exists)
        if (root->right != NULL) {
            root->right->val = root->val * 2 + 2;  // Assign new value
        }
        solve(root->right);
    }

    vector<int> values_list;  // Stores recovered values of the tree

    /**
     * Constructor initializes the recovery process of the tree.
     * - The root node is set to `0`.
     * - Calls `solve()` to restore the entire tree.
     */
    FindElements(TreeNode* root) {
        root->val = 0;  // Initialize root value to 0
        solve(root);
    }

    /**
     * Checks if a given `target` value exists in the recovered tree.
     * - Uses linear search to find the target in `values_list`.
     * - Returns `true` if found, otherwise `false`.
     */
    bool find(int target) {
        for (int i = 0; i < values_list.size(); i++) {
            if (target == values_list[i]) return true;  // Target found
        }
        return false;  // Target not found
    }
};

```
```javascript []
class FindElements {
    /**
     * Constructor initializes the recovery process of the tree.
     */
    constructor(root) {
        this.valuesList = new Set();
        root.val = 0;
        this.solve(root);
    }

    /**
     * Recursively restores the values of the tree nodes.
     */
    solve(root) {
        if (!root) return;

        // Store the restored value
        this.valuesList.add(root.val);

        // Process left child
        if (root.left) {
            root.left.val = root.val * 2 + 1;
        }
        this.solve(root.left);

        // Process right child
        if (root.right) {
            root.right.val = root.val * 2 + 2;
        }
        this.solve(root.right);
    }

    /**
     * Checks if a given `target` value exists in the recovered tree.
     */
    find(target) {
        return this.valuesList.has(target);
    }
}

```
```python []
class FindElements:
    def __init__(self, root):
        """Constructor initializes the recovery process of the tree."""
        self.values_list = set()
        root.val = 0
        self.solve(root)

    def solve(self, root):
        """Recursively restores the values of the tree nodes."""
        if not root:
            return
        
        # Store the restored value
        self.values_list.add(root.val)

        # Process left child
        if root.left:
            root.left.val = root.val * 2 + 1
        self.solve(root.left)

        # Process right child
        if root.right:
            root.right.val = root.val * 2 + 2
        self.solve(root.right)

    def find(self, target):
        """Checks if a given `target` value exists in the recovered tree."""
        return target in self.values_list

```
```Java []
import java.util.*;

class FindElements {
    private List<Integer> valuesList = new ArrayList<>();

    /**
     * Recursively restores the values of the tree nodes.
     */
    private void solve(TreeNode root) {
        if (root == null) {
            return; // Base case: If node is null, stop recursion
        }

        // Store the restored value
        valuesList.add(root.val);

        // Process left child
        if (root.left != null) {
            root.left.val = root.val * 2 + 1;
        }
        solve(root.left);

        // Process right child
        if (root.right != null) {
            root.right.val = root.val * 2 + 2;
        }
        solve(root.right);
    }

    /**
     * Constructor initializes the recovery process of the tree.
     */
    public FindElements(TreeNode root) {
        root.val = 0;
        solve(root);
    }

    /**
     * Checks if a given `target` value exists in the recovered tree.
     */
    public boolean find(int target) {
        return valuesList.contains(target);
    }
}

```



['Tree', 'Depth-First Search', 'Breadth-First Search', 'Design', 'Binary Tree', 'Interactive', 'C++', 'Java', 'Python3', 'JavaScript']