Beats 100% | Efficient Binary Tree Recovery | Bit Manipulation & Set Storage 🌳
Youtube🚀Beats 100% | Efficient Binary Tree Recovery | Bit Manipulation & Set Storage 🌳🔼 Please Upvote🔼 Please Upvote🔼 Please Upvote🔼 Please Upvote💡If this helpe
# Youtube
https://youtu.be/vmQHt247oxQ

![image.png](https://assets.leetcode.com/users/images/3da38627-99fd-46e4-ab40-e3224b7e7378_1740113757.651618.png)


---

# 🚀 **Beats 100% | Efficient Binary Tree Recovery | Bit Manipulation & Set Storage 🌳**

---

# **🔼 Please Upvote**  
# **🔼 Please Upvote**  
# **🔼 Please Upvote**  
# **🔼 Please Upvote**  

💡 **If this helped, don’t forget to upvote! 🚀🔥**  

---

### **💡 Problem Breakdown**  
Given a corrupted binary tree where all node values are initialized to `-1`, recover the tree such that:  
- The root node is set to `0`.  
- Left child = `2 * parent + 1`.  
- Right child = `2 * parent + 2`.

Implement a class `FindElements` with the following methods:
- **Constructor:** Recovers the tree by traversing and recalculating all node values.
- **`find(target)`:** Returns `true` if the target value is present in the recovered tree.

---

### **Approach Overview**  

- **Recovery:**  
  Recursively set each node's value using the given rules.  
  Store all recovered values in a data structure (`BitSet`, `set`, etc.) for fast lookup.  

- **Finding Values:**  
  Directly check if a target exists in the recovered data structure.

---

### **Why This Approach?**

1. **Guaranteed Correctness:**  
   The recovery rules ensure each node value is unique and correctly calculated.  

2. **Efficient Lookup:**  
   Using `BitSet` or `set` allows `O(1)` lookup time for the `find` method.

3. **Optimal Time Complexity:**  
   - Tree recovery takes `O(n)` time, where `n` is the number of nodes in the tree.  
   - Each `find` operation takes `O(1)` time.

---

### **Complexity Analysis**  
- **Time Complexity:**  
  - `O(n)` for recovery (traverse all nodes once).  
  - `O(1)` for each `find` operation.  

- **Space Complexity:**  
  - `O(n)` for storing all recovered node values.

---

## **📝 Code Implementations**

---

### **🔵 Java Solution**  
```java []


class FindElements {
    BitSet recoveredValues;

    public FindElements(TreeNode root) {
        root.val = 0;
        recoveredValues = new BitSet();
        recoverTree(root);
    }

    private void recoverTree(TreeNode root) {
        if (root == null) return;
        recoveredValues.set(root.val);
        if (root.left != null) {
            root.left.val = 2 * root.val + 1;
            recoverTree(root.left);
        }
        if (root.right != null) {
            root.right.val = 2 * root.val + 2;
            recoverTree(root.right);
        }
    }

    public boolean find(int target) {
        return recoveredValues.get(target);
    }
}
```

---

### **🟢 C++ Solution**  
```cpp []

class FindElements {
    unordered_set<int> recoveredValues;

    void recoverTree(TreeNode* root) {
        if (!root) return;
        recoveredValues.insert(root->val);
        if (root->left) {
            root->left->val = 2 * root->val + 1;
            recoverTree(root->left);
        }
        if (root->right) {
            root->right->val = 2 * root->val + 2;
            recoverTree(root->right);
        }
    }

public:
    FindElements(TreeNode* root) {
        root->val = 0;
        recoverTree(root);
    }

    bool find(int target) {
        return recoveredValues.count(target);
    }
};
```

---

### **🟣 Python3 Solution**  
```python []


class FindElements:
    def __init__(self, root):
        self.recoveredValues = set()
        root.val = 0
        self.recoverTree(root)

    def recoverTree(self, root):
        if not root:
            return
        self.recoveredValues.add(root.val)
        if root.left:
            root.left.val = 2 * root.val + 1
            self.recoverTree(root.left)
        if root.right:
            root.right.val = 2 * root.val + 2
            self.recoverTree(root.right)

    def find(self, target):
        return target in self.recoveredValues

```

---

### **🔴 JavaScript Solution**  
```javascript []

var FindElements = function(root) {
    this.recoveredValues = new Set();
    root.val = 0;
    this.recoverTree(root);
};

FindElements.prototype.recoverTree = function(root) {
    if (!root) return;
    this.recoveredValues.add(root.val);
    if (root.left) {
        root.left.val = 2 * root.val + 1;
        this.recoverTree(root.left);
    }
    if (root.right) {
        root.right.val = 2 * root.val + 2;
        this.recoverTree(root.right);
    }
};

FindElements.prototype.find = function(target) {
    return this.recoveredValues.has(target);
};
```

---

# **🔼 Please Upvote**  
# **🔼 Please Upvote**  
# **🔼 Please Upvote**  
# **🔼 Please Upvote**  

💡 **If this helped, don’t forget to upvote! 🚀🔥**  
['Bit Manipulation', 'Tree', 'Binary Search Tree', 'Binary Tree', 'C++', 'Java', 'Python3', 'JavaScript']