# Find Elements in a Contaminated Binary Tree
**Difficulty:** MEDIUM
[External](https://leetcode.com/problems/find-elements-in-a-contaminated-binary-tree)
Canonical: https://scaleengineer.com/dsa/problems/find-elements-in-a-contaminated-binary-tree
**Patterns:** [Design](https://scaleengineer.com/dsa/patterns/design)
**Algorithms:** [Depth-First Search](https://scaleengineer.com/algorithms/depth-first-search), [Breadth-First Search](https://scaleengineer.com/algorithms/breadth-first-search)
**Data structures:** Hash Table, Tree, Binary Tree
---
## Problem
Given a binary tree with the following rules:

1. `root.val == 0`
2. For any `treeNode`:  
  1. If `treeNode.val` has a value `x` and `treeNode.left != null`, then `treeNode.left.val == 2 * x + 1`
  2. If `treeNode.val` has a value `x` and `treeNode.right != null`, then `treeNode.right.val == 2 * x + 2`

Now the binary tree is contaminated, which means all `treeNode.val` have been changed to `-1`.

Implement the `FindElements` class:

* `FindElements(TreeNode* root)` Initializes the object with a contaminated binary tree and recovers it.
* `bool find(int target)` Returns `true` if the `target` value exists in the recovered binary tree.

**Example 1:**

![](https://assets.glich.co/dsa/find-elements-in-a-contaminated-binary-tree/image0.jpg) 

**Input**
["FindElements","find","find"]
[[[-1,null,-1]],[1],[2]]
**Output**
[null,false,true]
**Explanation**
FindElements findElements = new FindElements([-1,null,-1]); 
findElements.find(1); // return False 
findElements.find(2); // return True 

**Example 2:**

![](https://assets.glich.co/dsa/find-elements-in-a-contaminated-binary-tree/image1.jpg) 

**Input**
["FindElements","find","find","find"]
[[[-1,-1,-1,-1,-1]],[1],[3],[5]]
**Output**
[null,true,true,false]
**Explanation**
FindElements findElements = new FindElements([-1,-1,-1,-1,-1]);
findElements.find(1); // return True
findElements.find(3); // return True
findElements.find(5); // return False

**Example 3:**

![](https://assets.glich.co/dsa/find-elements-in-a-contaminated-binary-tree/image2.jpg) 

**Input**
["FindElements","find","find","find","find"]
[[[-1,null,-1,-1,null,-1]],[2],[3],[4],[5]]
**Output**
[null,true,false,false,true]
**Explanation**
FindElements findElements = new FindElements([-1,null,-1,-1,null,-1]);
findElements.find(2); // return True
findElements.find(3); // return False
findElements.find(4); // return False
findElements.find(5); // return True

**Constraints:**

* `TreeNode.val == -1`
* The height of the binary tree is less than or equal to `20`
* The total number of nodes is between `[1, 104]`
* Total calls of `find()` is between `[1, 104]`
* `0 <= target <= 106`

# Approaches
## Brute-Force Search on Each `find` Call
This approach avoids any pre-computation in the constructor. For each call to `find(target)`, it traverses the tree from the root, calculating the "recovered" value for each node on the fly. It checks if any of these calculated values match the target.
**Time:** Constructor: `O(1)`. `find(target)`: `O(N)`, where N is the number of nodes in the tree. In the worst case, we have to visit every node to find (or not find) the target. · **Space:** `O(H)`, where H is the height of the tree. This space is used by the recursion stack. In the worst case of a skewed tree, this can be `O(N)`.
**Pros:** Simple to understand and implement.; No upfront cost in the constructor (`O(1)` time).; Minimal memory usage (`O(H)` for recursion stack).
**Cons:** The `find` operation is very slow with a time complexity of `O(N)`, where N is the number of nodes.; For problems with a large number of `find` calls, this approach is highly likely to exceed the time limit.
### Explanation
The `FindElements` constructor simply stores a reference to the root of the contaminated tree. The `find(target)` method initiates a traversal (like Depth-First Search or Breadth-First Search) starting from the root. The root's recovered value is 0. For any node with a recovered value `x`, its left child's value is `2*x + 1` and its right child's value is `2*x + 2`. During the traversal, we keep track of the current node's correct value. If this value matches the `target`, we return `true`. If the entire tree is traversed without finding the target, we return `false`. This is essentially performing a new search on the conceptual recovered tree for every `find` call.

```java
class FindElements {
    private TreeNode root;

    public FindElements(TreeNode root) {
        this.root = root;
    }

    public boolean find(int target) {
        return dfs(root, 0, target);
    }

    private boolean dfs(TreeNode node, int currentValue, int target) {
        if (node == null || currentValue > target) {
            return false;
        }
        if (currentValue == target) {
            return true;
        }
        return dfs(node.left, 2 * currentValue + 1, target) ||
               dfs(node.right, 2 * currentValue + 2, target);
    }
}
```
### Algorithm
- In the `FindElements` constructor, simply store a reference to the root of the contaminated tree.
- The `find(target)` method initiates a traversal (like Depth-First Search) starting from the root.
- A recursive helper function, say `dfs(node, currentValue, target)`, is used for the traversal.
- The initial call is `dfs(root, 0, target)`.
- Inside the `dfs` function:
  - If the current `node` is `null`, or if `currentValue` is greater than `target`, return `false` as the target cannot be found in this subtree.
  - If `currentValue` equals `target`, return `true`.
  - Recursively call `dfs` for the left child with value `2 * currentValue + 1` and the right child with value `2 * currentValue + 2`.
  - Return `true` if either of the recursive calls finds the target.

## Path Reconstruction from Target
This approach leverages the mathematical relationship between a node's value and its parent's value. Instead of searching the tree for the target, we start from the `target` value and mathematically compute the path back to the root (value 0). Then, we verify if this computed path actually exists in the physical tree structure.
**Time:** Constructor: `O(1)`. `find(target)`: `O(H)` or `O(log target)`. The path reconstruction and the tree traversal both take a number of steps proportional to the depth of the target node, which is bounded by the tree height `H`. · **Space:** `O(H)` or `O(log target)`, where H is the tree height. This space is used to store the reconstructed path from the target to the root.
**Pros:** Very fast `find` operation with `O(H)` complexity.; Instantaneous constructor (`O(1)`).; Excellent space efficiency, using only `O(H)` extra space.
**Cons:** The logic is more complex to implement compared to other approaches.; Each `find` call requires `O(H)` time, which is slower than the `O(1)` of the pre-computation approach.
### Explanation
The key insight is that for any node with value `v > 0`, its parent's value is `(v - 1) / 2` (using integer division). The constructor only needs to store the root of the tree. The `find(target)` method first reconstructs the path from the target to the root by repeatedly calculating the parent. For a value `c`, it's a left child if odd and a right child if even. After building the path, we traverse the actual tree from the root, following these directions. If we ever encounter a `null` node, the path doesn't exist. If we successfully complete the traversal, the node exists.

```java
class FindElements {
    private TreeNode root;

    public FindElements(TreeNode root) {
        this.root = root;
    }

    public boolean find(int target) {
        if (target < 0) {
            return false;
        }
        
        TreeNode node = this.root;
        int current = target;
        
        // We can check the path while reconstructing it to save space
        // We need to find the path from root to target, so we first find the path from target to root
        // and then traverse it backwards. A simpler way is to use binary representation of (target+1)
        // The path from root to a node with value `x` is encoded in the binary representation of `x+1`.
        // For example, for target=4, 4+1=5, binary is 101. Ignore the leading 1. Path is R, L.
        // 0 -> right -> 2 -> left -> 5. No, this is not correct. Let's stick to path reconstruction.
        
        java.util.Deque<Integer> path = new java.util.ArrayDeque<>();
        while (current > 0) {
            path.push(current);
            current = (current - 1) / 2;
        }

        while (!path.isEmpty()) {
            if (node == null) return false;
            int val = path.pop();
            if (val % 2 == 1) { // Left child
                node = node.left;
            } else { // Right child
                node = node.right;
            }
        }
        return node != null;
    }
}
```
### Algorithm
- In the constructor, just save the `root` node.
- In the `find(target)` method:
  - Handle edge cases: if `target < 0`, return `false`. If `target == 0`, return `true`.
  - Reconstruct the path from the `target` up to the root (value 0). Start with `current = target`.
  - In a loop, while `current > 0`, determine if `current` is a left or right child and add the direction to a list. Then update `current` to its parent's value: `parent = (current - 1) / 2`.
  - After the path is built, traverse the actual tree from the `root` following the path directions in reverse order.
  - If at any point the traversal leads to a `null` node, the path is invalid. Return `false`.
  - If the traversal completes successfully, the node exists. Return `true`.

## Pre-computation and Storage in a HashSet
This approach prioritizes the speed of the `find` operation by doing all the work upfront in the constructor. It recovers the entire tree, calculates the correct value for every node, and stores all these values in a `HashSet` for near-instantaneous lookups.
**Time:** Constructor: `O(N)`, where N is the number of nodes. We must visit every node once. `find(target)`: `O(1)` on average, as `HashSet.contains` is a constant-time operation. · **Space:** `O(N)`, where N is the number of nodes. This space is required to store all the recovered node values in the `HashSet`.
**Pros:** Extremely fast `find` operation, `O(1)` on average.; Ideal for scenarios with a large number of `find` queries.; The implementation logic is relatively straightforward.
**Cons:** The constructor has a time complexity of `O(N)`, which involves a full tree traversal and can be slow for very large trees.; Requires `O(N)` extra space to store all the node values, which might be a concern for memory-constrained environments.
### Explanation
In the `FindElements` constructor, we traverse the entire contaminated tree, for example, using a recursive Depth-First Search (DFS). We maintain a `HashSet` to store the recovered values. The traversal starts at the root, which is assigned the value 0. This value is added to the set. For any node with a calculated value `x`, we recursively visit its left child with the value `2*x + 1` and its right child with the value `2*x + 2`. The calculated values for these children are also added to the set. After the constructor finishes, the `HashSet` contains all the valid node values in the recovered tree. The `find(target)` method then becomes a simple and extremely fast operation: it just checks if the `target` exists in the `HashSet`.

```java
import java.util.HashSet;
import java.util.Set;

class FindElements {
    private Set<Integer> values = new HashSet<>();

    public FindElements(TreeNode root) {
        recover(root, 0);
    }

    private void recover(TreeNode node, int val) {
        if (node == null) {
            return;
        }
        values.add(val);
        recover(node.left, 2 * val + 1);
        recover(node.right, 2 * val + 2);
    }

    public boolean find(int target) {
        return values.contains(target);
    }
}
```
### Algorithm
- Initialize a `HashSet<Integer>` as a member variable to store recovered values.
- In the `FindElements` constructor, traverse the entire tree using a recursive helper function, e.g., `recover(node, val)`.
- The initial call is `recover(root, 0)`.
- The `recover` function:
  - Base case: If `node` is `null`, return.
  - Add the current `val` to the `HashSet`.
  - Recursively call `recover(node.left, 2 * val + 1)`.
  - Recursively call `recover(node.right, 2 * val + 2)`.
- In the `find(target)` method, simply check if the `target` is present in the `HashSet` using `contains()` and return the result.

# Solutions
### Java

```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 > vis = new HashSet <>(); public FindElements ( TreeNode root ) { root . val = 0 ; dfs ( root ); } private void dfs ( TreeNode root ) { vis . add ( root . val ); if ( root . left != null ) { root . left . val = root . val * 2 + 1 ; dfs ( root . left ); } if ( root . right != null ) { root . right . val = root . val * 2 + 2 ; dfs ( root . right ); } } public boolean find ( int target ) { return vis . contains ( target ); } } /** * Your FindElements object will be instantiated and called as such: * FindElements obj = new FindElements(root); * boolean param_1 = obj.find(target); */
```

### JavaScript

```javascript
/** * Definition for a binary tree node. * function TreeNode(val, left, right) { * this.val = (val===undefined ? 0 : val) * this.left = (left===undefined ? null : left) * this.right = (right===undefined ? null : right) * } */ const s =
  Symbol.for(" s ");
/** * @param {TreeNode} root */ var FindElements = function (root) {
  root.val = 0;
  this[s] = new Set();
  const dfs = (node, x = 0) => {
    if (!node) return;
    this[s].add(x);
    dfs(node.left, x * 2 + 1);
    dfs(node.right, x * 2 + 2);
  };
  dfs(root);
};
/** * @param {number} target * @return {boolean} */ FindElements.prototype.find =
  function (target) {
    return this[s].has(target);
  }; /** * Your FindElements object will be instantiated and called as such: * var obj = new FindElements(root) * var param_1 = obj.find(target) */

```

### CPP

```cpp
/** * 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: FindElements ( TreeNode * root ) { root -> val = 0 ; function < void ( TreeNode * ) > dfs = [ & ]( TreeNode * root ) { vis . insert ( root -> val ); if ( root -> left ) { root -> left -> val = root -> val * 2 + 1 ; dfs ( root -> left ); } if ( root -> right ) { root -> right -> val = root -> val * 2 + 2 ; dfs ( root -> right ); } }; dfs ( root ); } bool find ( int target ) { return vis . count ( target ); } private: unordered_set < int > vis ; }; /** * Your FindElements object will be instantiated and called as such: * FindElements* obj = new FindElements(root); * bool param_1 = obj->find(target); */
```

### Python

```python
# Definition for a binary tree node. # class TreeNode: # def __init__(self, val=0, left=None, right=None): # self.val = val # self.left = left # self.right = right class FindElements : def __init__ ( self , root : Optional [ TreeNode ]): def dfs ( root ): self . vis . add ( root . val ) if root . left : root . left . val = root . val * 2 + 1 dfs ( root . left ) if root . right : root . right . val = root . val * 2 + 2 dfs ( root . right ) root . val = 0 self . vis = set () dfs ( root ) def find ( self , target : int ) -> bool : return target in self . vis # Your FindElements object will be instantiated and called as such: # obj = FindElements(root) # param_1 = obj.find(target)
```