O(n) python solution with step by step explanation
IntuitionWe can solve this problem using both bfs and dfs but we will solve it using dfs. Because we have to solve it in top down approach as to find a child no
# Intuition
We can solve this problem using both bfs and dfs but we will solve it using dfs. Because we have to solve it in top down approach as to find a child node's value, we must find the parent node's value first. Tree traversal is done in many types but we need preorder traversal in this case as it says we must function at root node, then left child and right child.

As the problem says we have contaminated binary tree so it's values are -1. So, we must revert it to the original form using the given formula:
-> l = 2 * x + 1
-> r = 2 * x + 2
assuming x to be zero

So, we first find elements[-1,-1,-1,-1,-1] and find the elemnts. If they match, we return True and if they don't, we return False

# Approach
So, we will begin by creating a set named targets which will store all the values. And, we will begin our dfs search from root. After that, we will create a dfs helper function to solve the problem like from root 0 to 1 to 3 and again 1 and then to 4 and back to 1 and back to 0 and go to 2.

We will also cover a scenario in which a node has no left or right to go, we return back. But they are nodes to the left and to the right, we add them to our set. We can iterate through them using the formula given above.
To end it, we return the target from our targets set.

# Example of the Operation:
["FindElements","find","find","find"]
[[[-1,-1,-1,-1,-1]],[1],[3],[5]]

So, this is the input we're given. To solve it, we are given a contaminated tree containing values -1. We will create a targets set.
-> targets = set()

We will assume the parent node to be 0.
-> l = 2 * x + 1
-> r = 2 * x + 2
These are the formulas given after solving, we will store them into our targets set.

From 0:
-> l = 2 * 0 + 1 = 0 + 1 = 1
-> targets = {1}

So, we found a child node as we're doing dfs we will try to go deep as possible until we're out of left and right children nodes.

From 1:
-> l = 2 * 1 + 1 = 2 + 1 = 3
-> targets = {1,3}

We found the left child node and we go up to 1 again and find its right child node.
-> r = 2 * 1 + 2 = 2 + 2 = 4
-> targets = {1,3,4}

We found the right child node and now, we go up to 1 again but we can see that we already found it's children so we back to 0 and try to find it's right child node:
-> r = 2 * 0 + 2 = 0 + 2 = 2
-> targets = {1,3,4,2}

And 2, doesn't have any children nodes. So, the first find query says find [1], it's present in our set. So, we return True.

Next is find[3], it's present in our set. So, we return True.

And at last, it is find[5] which doesn't exist in our set. So, we return False.

![Screenshot 2025-02-21 at 7.21.48 PM.png](https://assets.leetcode.com/users/images/7474d684-db05-452c-939a-8b50e90724d6_1740145957.5002918.png)


# Complexity
- Time complexity:
O(n) where n denotes the number of nodes in the tree because we're searching and recovering the tree which can take up 'n' time

- Space complexity:
O(n) because we are using set named targets which can take up to 'n' amount of space

# Code
```python3 []
# 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]):
        self.targets = set() #hashsets
        self.dfs(root, 0) #dfs search

    def find(self, target: int) -> bool:
        return target in self.targets #return target or else we return false
        
    def dfs(self, node, value): #dfs helper func
        if node is None: #none ie when we search for left and right but they don't do exist so we return none
            return
        self.targets.add(value) #if they exist, we add that value to the set
        self.dfs(node.left, value * 2 + 1) #recursive dfs search
        self.dfs(node.right, value * 2 + 2) #recovery operation for both

# Your FindElements object will be instantiated and called as such:
# obj = FindElements(root)
# param_1 = obj.find(target)
```
['Python3']