Given a binary tree with the following rules:

root.val == 0
If treeNode.val == x and treeNode.left != null, then treeNode.left.val == 2 * x + 1
If treeNode.val == 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.
You need to first recover the binary tree and then implement the FindElements class:

FindElements(TreeNode* root) Initializes the object with a contamined binary tree, you need to recover it first.
bool find(int target) Return if the target value exists in the recovered binary tree.

 
Example 1:

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:

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:

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, 10^4]
Total calls of find() is between [1, 10^4]
0 <= target <= 10^6

Difficulty: interview

Starter code:

# 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: TreeNode):
    def find(self, target: int) -> bool:
# Your FindElements object will be instantiated and called as such:
# obj = FindElements(root)
# param_1 = obj.find(target)

Solutions:
# 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: TreeNode):
      self.dicts = {}
      if root:
        root.val = 0
        stacks = [root]
        self.dicts[0] = 1
        while stacks:
          new_stacks = []
          for element in stacks:
            if element.left: element.left.val = element.val*2 + 1; new_stacks.append(element.left);\\
               self.dicts[element.left.val] = 1
            if element.right: element.right.val = element.val*2 + 2; new_stacks.append(element.right);\\
               self.dicts[element.right.val] = 1
          stacks = new_stacks
        #print (self.dicts)
        
        

    def find(self, target: int) -> bool:
        return target in self.dicts


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

# 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: TreeNode):
        self.ss = set()
        self.restoreTree(root, 0)
        
        
    def restoreTree(self, root: TreeNode, val: int):
        if not root: return
        else: 
            root.val = val
            self.ss.add(val)
        if root.left: self.restoreTree(root.left, 2 * val + 1)
        if root.right: self.restoreTree(root.right, 2 * val + 2)
        return

    def find(self, target: int) -> bool:
        return target in self.ss
    \"\"\"\"
        root = self.root
        if not root: return False
        if root.val == target: return True
        left, right = False, False
        if root.left: left = self.findItem(target, root.left)
        if root.right: right = self.findItem(target, root.right)
        return left or right
        


    def findItem(self, target: int, root: TreeNode):
        if not root: return False
        if root.val == target: return True
        left, right = False, False
        if root.left: left = self.findItem(target, root.left)
        if root.right: right = self.findItem(target, root.right)
        return left or right
        
\"\"\"
# Your FindElements object will be instantiated and called as such:
# obj = FindElements(root)
# param_1 = obj.find(target)

# 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: TreeNode):
        self.root = root
        self.values = set()
        def recover(head, val):
            if head is None:
                return
            head.val = val
            self.values.add(val)
            recover(head.left, val * 2 + 1)
            recover(head.right, val * 2 + 2)
        recover(root, 0)

    def find(self, target: int) -> bool:
        return target in self.values
            

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


# 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: TreeNode):
        self.root = root
        
    def find(self, target: int) -> bool:
        
        stack=[]
        if target ==0 and self.root:
            return True
        
        while target>0:
            if target%2:
                target=(target-1)/2
                stack.append(\"left\")
            else:
                target=(target-2)/2
                stack.append(\"right\")
                
        node=self.root
        if not node or not stack:
            return False
        
        while stack:
            path=stack.pop()
            if path==\"left\":
                node=node.left
                if not node:
                    return False
            else:
                node=node.right
                if not node:
                    return False
        return True
        
        
        
        
        
        
        
        
        
        
        
        # q=[self.root]
        # while q:
        #     width=len(q)
        #     for _ in range(width):
        #         node=q.pop(0)
        #         if node.val == target:
        #             return True
        #         if node.left:
        #             node.left.val=node.val*2+1
        #             q.append(node.left)
        #         if node.right:
        #             node.right.val=node.val*2+2
        #             q.append(node.right)
        # return False
    
    # def fix_tree(self,root,val):
    #     if not root:
    #         return None
    #     root.val=val
    #     root.left=self.fix_tree(root.left,val*2+1)
    #     root.right=self.fix_tree(root.right,val*2+2)
    #     self.max = max(self.max,val)
    #     return root


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

# 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: TreeNode):
        def recover(root, val):
            root.val = val
            if root.left:
                recover(root.left, 2*val+1)
            if root.right:
                recover(root.right, 2*val+2)
        recover(root, 0)
        self._root = root

    def find(self, target: int) -> bool:
        ops = []
        while target > 0:
            if target % 2 == 1:
                ops = [\"l\"] + ops
                target = (target-1)//2
            else:
                ops = [\"r\"] + ops
                target = (target-2)//2
        assert target==0
        node = self._root
        for op in ops:
            node = node.left if op == 'l' else node.right
            if not node:
                return False
        return True
            
        


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

# 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 recover(self, root, val):
        root.val = val
        if root.left:
            self.recover(root.left, 2*val+1)
        if root.right:
            self.recover(root.right, 2*val+2)
    
    def __init__(self, root: TreeNode):
        self.recover(root, 0)
        self._root = root

    def find(self, target: int) -> bool:
        ops = []
        while target > 0:
            if target % 2 == 1:
                ops = [\"l\"] + ops
                target = (target-1)//2
            else:
                ops = [\"r\"] + ops
                target = (target-2)//2
        assert target==0
        node = self._root
        for op in ops:
            node = node.left if op == 'l' else node.right
            if not node:
                return False
        return True
            
        


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

# 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: TreeNode):
        self.root = root
        values = set()
        def recover(head, val):
            if head is None:
                return
            head.val = val
            values.add(val)
            recover(head.left, val * 2 + 1)
            recover(head.right, val * 2 + 2)
        recover(root, 0)
        self.values = values

    def find(self, target: int) -> bool:
        return target in self.values
            

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


# 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

def recover(root: TreeNode):
    x = root.val 
    if root.left:
        root.left.val = 2*x+1
        recover(root.left)
    if root.right:
        root.right.val = 2*x+2
        recover(root.right)
        
def get_path(n: int) -> List[int]:
    # x = 2*(2*(2*(2*0 + a) + b) + c) + d
    # x = 2*(2*(2*a + b) + c) + d
    # x = 2*(4*a + 2*b + c) + d
    # x = 8*a + 4*b + 2*c + d
    
    # x % 2 = 0 + 0 + 0 + (d%2)
    # if d == 1 -> d%2 = 1
    # if d == 2 -> d%2 = 0
    
    result = []
    while n > 0:
        if n % 2 == 0:
            digit = 2
        else:
            digit = 1
        
        result.append(digit)
        n -= digit
        n //= 2
    return result
        
        
def find(root: TreeNode, path: List[int]) -> bool:
    if root is None:
        return False
    
    if not path:
        return True
    
    direction = path.pop()
    if direction == 1:
        if root.left:
            root.left.val = 2*root.val+1
        return find(root.left, path)
    elif direction == 2:
        if root.right:
            root.right.val = 2*root.val+2
        return find(root.right, path)
    
    return False


class FindElements:
    def __init__(self, root: TreeNode):
        root.val = 0
        # recover(root)
        self.tree = root

    def find(self, target: int) -> bool:
        self.tree.val = 0 
        p = get_path(target)
        return find(self.tree, p)
        


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


# 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

def get_path(n: int) -> List[int]:
    # x = 2*(2*(2*(2*0 + a) + b) + c) + d
    # x = 2*(2*(2*a + b) + c) + d
    # x = 2*(4*a + 2*b + c) + d
    # x = 8*a + 4*b + 2*c + d
    
    # x % 2 = 0 + 0 + 0 + (d%2)
    # if d == 1 -> d%2 = 1
    # if d == 2 -> d%2 = 0
    
    result = []
    while n > 0:
        if n % 2 == 0:
            digit = 2
        else:
            digit = 1
        
        result.append(digit)
        n -= digit
        n //= 2
    return result
        
        
def find(root: TreeNode, path: List[int]) -> bool:
    if root is None:
        return False
    
    if not path:
        return True
    
    direction = path.pop()
    if direction == 1:
        if root.left:
            root.left.val = 2*root.val+1
        return find(root.left, path)
    elif direction == 2:
        if root.right:
            root.right.val = 2*root.val+2
        return find(root.right, path)
    
    return False


class FindElements:
    def __init__(self, root: TreeNode):
        root.val = 0
        self.tree = root

    def find(self, target: int) -> bool:
        p = get_path(target)
        return find(self.tree, p)
        


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


# 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 helper(self, root, level):
        if not root:
            return None
        if level == 0:
            root.val = 0
            self.mem.add(root.val)
        if root.left:
            root.left.val = root.val * 2 + 1
            root.left = self.helper(root.left, level + 1)
            self.mem.add(root.left.val)
        if root.right:
            root.right.val = root.val * 2 + 2
            root.right = self.helper(root.right, level + 1)
            self.mem.add(root.right.val)
        return root
    
    def __init__(self, root: TreeNode):
        self.mem = set()
        self.helper(root, 0)
        
        

    def find(self, target: int) -> bool:
        return target in self.mem


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


from math import floor
from math import ceil
from math import sqrt
from collections import deque
import numpy
from _collections import deque
#from _ast import Num # LC doesn't like this
from heapq import *
from typing import List
import random

MOD = int(1e9 + 7)
BASE = 256

def dfs(root, rv, s):
    if not root:
        return
    s.add(rv)
    dfs(root.left, 2 * rv + 1, s)
    dfs(root.right, 2 * rv + 2, s)

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: TreeNode):
        self.s = set()
        dfs(root, 0, self.s)

    def find(self, target: int) -> bool:
        return target in self.s


\"\"\"
\"\"\"

# 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 recover(self, node, x):
        if node is None: return
        node.val = x
        self.vals.add(node.val)
        self.recover(node.left, (2*node.val)+1)
        self.recover(node.right, (2*node.val)+2)

    def __init__(self, root: TreeNode):
        root.val = 0
        self.vals = set()
        self._root = root
        self.recover(root, 0)

    def find(self, target: int) -> bool:
        return target in self.vals


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


# 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: TreeNode):
        
        self.vals = set()
        
        def build(root, x):
            root.val = x
            self.vals.add(x)
            if root.left:
                build(root.left, 2*x + 1)
            if root.right:
                build(root.right, 2*x + 2)
            
        build(root, 0)
        

    def find(self, target: int) -> bool:
        return target in self.vals


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


# 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: TreeNode):
        self.r = root
        def helper(node, value):
            node.val = value
            if node.left:
                helper(node.left, value * 2 + 1)
            if node.right:
                helper(node.right, value * 2 + 2)
        helper(root, 0)
       

    def find(self, target: int) -> bool:
        path = target
        stack = []
        while path:
            stack.append(path)
            if path % 2 == 0:
                path -= 2
                if path != 0:
                    path //= 2
            else:
                path -= 1
                if path != 0:
                    path //= 2
        stack.append(0)
        
        def finder(s, root):
            
            if not s:
                return True
            if not root:
                return False
            value = s.pop()
            if root.val == value:
                if s:
                    if s[-1] % 2 == 0:
                        return finder(s, root.right)
                    else:
                        return finder(s, root.left)
                else:
                    return True
            else:
                return False
        return finder(stack, self.r)
            
        


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


# 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 dfs_recover(self, root: TreeNode):
        if not root:
            return
        
        if root.left is not None:
            root.left.val = 2 * root.val + 1
            self.all_values.add(root.left.val)
        
        if root.right is not None:
            root.right.val = 2 * root.val + 2
            self.all_values.add(root.right.val)
            
        self.dfs_recover(root.left)
        self.dfs_recover(root.right)
            
    
    def __init__(self, root: TreeNode):
        self.all_values = {}
        if root:
            root.val = 0
            self.all_values = {root.val,}
        self.dfs_recover(root)

    def find(self, target: int) -> bool:
        return target in self.all_values


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



class FindElements:
    def __init__(self, root: TreeNode):
        self.root = root
        self.exists = set()

        def inner(node: TreeNode, my_val: int):            
            self.exists.add(my_val)
            if node.left:
                inner(node.left, 2 * my_val + 1)
            if node.right:
                inner(node.right, 2 * my_val + 2)

        inner(self.root, 0)

    def find(self, target: int) -> bool:
        return target in self.exists


# 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: TreeNode):
        li=['null']
        self.y=set()
        def dfs(root,v):
            if(root):
                root.val=v
                self.y.add(root.val)
                dfs(root.left,2*v+1)
                dfs(root.right,2*v+2)
        dfs(root,0)
        print((self.y))
    def find(self, target: int) -> bool:
        if target in self.y:
            return True
        else:
            return False
        


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


# 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: TreeNode):
        self.array = {}
        self.populate_array(root, 0)
        
    def populate_array(self, node, count):
        if not node:
            return
        
        self.array[count] = True
        self.populate_array(node.left, count * 2 + 1)
        self.populate_array(node.right, count * 2 + 2)
        

    def find(self, target: int) -> bool:
        return target in self.array


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



class FindElements:
    def __init__(self, root: TreeNode):
        self.root = root
        self.exists = set()

        def inner(node: TreeNode, my_val: int):
            if not node:
                return

            self.exists.add(my_val)
            inner(node.left, 2 * my_val + 1)
            inner(node.right, 2 * my_val + 2)

        inner(self.root, 0)

    def find(self, target: int) -> bool:
        return target in self.exists


# 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: TreeNode):
        
        self.root = root
        self.container = set()
        
        def helper(root, val):

            if not root:
                return
            
            root.val = val
            #self.container.add(val)
            helper(root.left, root.val*2+1)
            helper(root.right, root.val*2+2)
                
        
        helper(self.root, 0)
        #print(self.root.val)
        return
            
    def find(self, target: int) -> bool:
        #遍历, 太慢
        #def bianli(root, target):
        #    if not root:
        #        return False
        #    
        #    if root.val == target:
        #        return True
        #    
        #    res = bianli(root.left,target) or bianli(root.right,target)
        #    return res
        #
        #return bianli(self.root, target)
        
        #因为这个tree的点不重复，所以可以找出唯一路径到target
        #那么将这个路径走一遍，如果不通就说明找不到
        
        def findpath(target):
            path = [target]
            while target:
                diff = 1 if target%2 else 2
                target = int((target - diff)/2)
                path.append(target)
                
            return path[::-1]
                
            
        def trav(node, depth, path):
            if depth> len(path):
                return False
            else:
                if not node:
                    return False
                if node.val == path[-1]:
                    return True
                #print(node.val)
                if node.val == path[depth]:
                    res = trav(node.left, depth+1, path) or trav(node.right, depth+1,path)
                    return res
            return False
        
                    
        path = findpath(target)
        #print(path)
        return trav(self.root, 0, path)
        
        # 还有种办法就是init的时候建个dict
        # 找的时候直接在dict里找
        # return target in self.container
                
            
            
            
            
        
            


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


# 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, R: TreeNode):
        R.val, V = 0, set()
        def dfs(R):
            if R == None or R.left is R.right: return
            if R.left != None: R.left.val, _ = 2*R.val + 1, V.add(2*R.val + 1)
            if R.right != None: R.right.val, _ = 2*R.val + 2, V.add(2*R.val + 2)
            dfs(R.left), dfs(R.right)
        dfs(R)
        self.V = V
    def find(self, t: int) -> bool: return t in self.V
        

#     def find(self, target: int) -> bool:
#         return target in self.set
        


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


# 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: TreeNode):
        
        self.root = root
        
        def helper(root, val):

            if not root:
                return
            
            root.val = val
            helper(root.left, root.val*2+1)
            helper(root.right, root.val*2+2)
                
        
        helper(self.root, 0)
        #print(self.root.val)
        return
            
    def find(self, target: int) -> bool:
        #遍历, 太慢
        #def bianli(root, target):
        #    if not root:
        #        return False
        #    
        #    if root.val == target:
        #        return True
        #    
        #    res = bianli(root.left,target) or bianli(root.right,target)
        #    return res
        #
        #return bianli(self.root, target)
        
        #因为这个tree的点不重复，所以可以找出唯一路径到target
        #那么将这个路径走一遍，如果不通就说明找不到
        
        def findpath(target):
            path = [target]
            while target:
                diff = 1 if target%2 else 2
                target = int((target - diff)/2)
                path.append(target)
                
            return path[::-1]
                
            
        def trav(node, depth, path):
            if depth> len(path):
                return False
            else:
                if not node:
                    return False
                if node.val == path[-1]:
                    return True
                #print(node.val)
                if node.val == path[depth]:
                    res = trav(node.left, depth+1, path) or trav(node.right, depth+1,path)
                    return res
                    
        path = findpath(target)
        #print(path)
        return trav(self.root, 0, path)
            
                
            
            
            
            
        
            


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


class FindElements:

    def __init__(self, root: TreeNode):
        self.value_set = set()
        root.val = 0
        self.recover_tree(root)

    def recover_tree(self, root):
        if root:
            self.value_set.add(root.val)
            if root.left:
                root.left.val = 2 * root.val + 1
                self.recover_tree(root.left)
            if root.right:
                root.right.val = 2 * root.val + 2
                self.recover_tree(root.right)
        return root

    def find(self, target: int) -> bool:
        return target in self.value_set

# 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

def revalue(n, v):
    if n is None:
        return
    n.val = v
    revalue(n.left, 2*v + 1)
    revalue(n.right, 2*v + 2)
    
class FindElements:

    def __init__(self, root: TreeNode):
        self.root = root
        revalue(root, 0)        

    def find(self, target: int) -> bool:
        if target == 0:
            return self.root is not None
        path = []
        otarget = target
        while target:
            branch = target % 2
            target //= 2
            if branch == 0:
                target -= 1
            path.append(branch)
        n = self.root
        while path:
            if path.pop():
                n = n.left
            else:
                n = n.right
            if n is None:
                return False
            if n.val == otarget:
                return True                
        return False


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


# 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 recover(self, node):
        if not node: 
            return
        self.memo |= 1 << node.val
        if node.left:
            node.left.val = 2 * node.val + 1
            self.recover(node.left)
        if node.right:
            node.right.val = 2 * node.val + 2
            self.recover(node.right)

    def __init__(self, root: TreeNode):
        self.root = root
        self.root.val = 0
        self.memo = 0
        self.recover(self.root)
        
    def find(self, target: int) -> bool:
        return self.memo & (1 << target) != 0
        
        


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


# 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 __decontaminate(self, node, val):
        if not node:
            return
        node.val = val
        self.__decontaminate(node.left, 2*node.val + 1)
        self.__decontaminate(node.right, 2*node.val + 2)
        
    def __init__(self, root: TreeNode):
        self.__decontaminate(root, 0)
        self.root = root
    
    def __trav(self, node, index, path):
        if index == len(path):
            return True
        if not node:
            return False
        if path[index] == node.val:
            l = self.__trav(node.left, index+1, path)
            r = self.__trav(node.right, index+1, path)
            return l or r
        else:
            return False
        
    def find(self, target: int) -> bool:
        path = [target]
        while target:
            diff = 1 if target%2 else 2
            target = int((target-diff)/2)
            path.append(target)
        path.reverse()
        return self.__trav(self.root, 0, path)

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


# 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: TreeNode):
        self.root = root
        res = []
        def helper(node, parent = None, left = False, right = False):
            if node:
                if parent is None:
                    node.val = 0 #root
                    res.append(node.val)
                else:
                    if left:
                        node.val = parent.val*2 + 1
                        res.append(node.val)
                    if right:
                        node.val = parent.val*2 + 2
                        res.append(node.val)
                helper(node.left, node, True, False)
                helper(node.right, node, False, True)
        helper(root)
        self.res = set(res)
        print(root)
        

    def find(self, target: int) -> bool:
        return target in self.res


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


# 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: TreeNode):
        self.root = root
        res = []
        def helper(node, parentVal = None, left = False, right = False):
            if node:
                if parentVal is None:
                    # node.val = 0 #root
                    val = 0
                    res.append(val)
                else:
                    if left:
                        # node.val = parent.val*2 + 1
                        val = parentVal*2 + 1
                        res.append(val)
                    if right:
                        # node.val = parent.val*2 + 2
                        val = parentVal*2 + 2
                        res.append(val)
                helper(node.left, val, True, False)
                helper(node.right, val, False, True)
        helper(root)
        self.res = set(res)
        print(root)
        

    def find(self, target: int) -> bool:
        return target in self.res


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


# 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: TreeNode):
        self.root = root
        res = {}
        def helper(node, parent = None, left = False, right = False):
            if node:
                if parent is None:
                    node.val = 0 #root
                    res[node.val] = 1
                else:
                    if left:
                        node.val = parent.val*2 + 1
                        res[node.val] = 1
                    if right:
                        node.val = parent.val*2 + 2
                        res[node.val] = 1
                helper(node.left, node, True, False)
                helper(node.right, node, False, True)
        helper(root)
        self.res = res
        print(root)
        

    def find(self, target: int) -> bool:
        return target in self.res


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


# 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: TreeNode):
        def helper(node, v):
            if node is None:
                return
            node.val = v
            if node.left:
                helper(node.left, v * 2 + 1)
            if node.right:
                helper(node.right, v * 2 + 2)
            return
        self.root = root
        helper(root, 0)
        print((self.root))
        return

    def find(self, target: int) -> bool:
        target += 1
        s = target
        l = 0;
        while target > 0:
            target = target >> 1
            l += 1
        node = self.root
        c = 0
        for c in range(1, l)[::-1]:  # 2, 1 for 111
            k = s & (1 << (c - 1))
            if k:
                if node.right:
                    node = node.right
                else:
                    return False
            else:
                if node.left:
                    node = node.left
                else:
                    return False
        return node and node.val == s - 1
                     
        


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


# 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 recoverTree(self, node: TreeNode, val: int) -> None: 
        if node:
            node.val = val
            self.num_set.add(val)
            self.recoverTree(node.left, 2 * val + 1)
            self.recoverTree(node.right, 2 * val + 2)
            
        '''
        if not node.left and not node.right:
            return None
        if node.left:
            node.left.val = 2 * node.val + 1
            self.num_set.add(node.left.val)
            self.recoverTree(node.left)
        if node.right:
            node.right.val = 2 * node.val + 2
            self.num_set.add(node.right.val)
            self.recoverTree(node.right)
        '''
        
    def __init__(self, root: TreeNode):
        self.num_set = set()
        self.num_set.add(0)
        
        self.recoverTree(root, 0)
        self.root = root       

    def find(self, target: int) -> bool:
        if target < self.root.val:
            return False
        return target in self.num_set


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


# 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 FindElementsDict:

    def dfs_recover(self, root: TreeNode):
        if not root:
            return
        
        if root.left is not None:
            root.left.val = 2 * root.val + 1
            self.all_values.add(root.left.val)
        
        if root.right is not None:
            root.right.val = 2 * root.val + 2
            self.all_values.add(root.right.val)
            
        self.dfs_recover(root.left)
        self.dfs_recover(root.right)
            
    
    def __init__(self, root: TreeNode):
        self.all_values = {}
        if root:
            root.val = 0
            self.all_values = {root.val,}
        self.dfs_recover(root)

    def find(self, target: int) -> bool:
        return target in self.all_values

class FindElements:

    def dfs_recover(self, root: TreeNode):
        if not root:
            return
        
        if root.left is not None:
            root.left.val = 2 * root.val + 1
            self.all_values[root.left.val] = True
        
        if root.right is not None:
            root.right.val = 2 * root.val + 2
            self.all_values[root.right.val] = True
            
        self.dfs_recover(root.left)
        self.dfs_recover(root.right)
            
    
    def __init__(self, root: TreeNode):
        self.all_values = [False] * 2097152 # 2<<20 = 2097152
        if root:
            root.val = 0
            self.all_values[root.val] = True
        self.dfs_recover(root)

    def find(self, target: int) -> bool:
        return self.all_values[target]


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


# 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: TreeNode):
        def helper(node, v):
            if node is None:
                return
            node.val = v
            if node.left:
                helper(node.left, v * 2 + 1)
            if node.right:
                helper(node.right, v * 2 + 2)
            return
        self.root = root
        helper(root, 0)
        print((self.root))
        return

    def find(self, target: int) -> bool:
        target += 1
        s = target
        l = 0;
        while target > 0:
            target = target >> 1
            l += 1
        node = self.root
        c = 0
        print((bin(s)))
        for c in range(1, l)[::-1]:  # 2, 1 for 111
            k = s & (1 << (c - 1))
            print(k)
            if k:
                if node.right:
                    node = node.right
                    print((node.val, s-1))
                else:
                    return False
            else:
                if node.left:
                    node = node.left
                else:
                    return False
        return node and node.val == s - 1
                     
        


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


# 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: TreeNode):
        root.val = 0
        root = self.recover(root)
        self.root = root
        self.inorder = self.Inorder(root)

    def recover(self, root: TreeNode) -> TreeNode:
        if root is None:
            return
        if root.left:
            root.left.val = 2*root.val + 1
        if root.right:
            root.right.val = 2*root.val + 2
            
        self.recover(root.left)
        self.recover(root.right)
        
        return root
    
    def Inorder(self, root):
        lis = []
        if root:
            lis = self.Inorder(root.left)
            lis.append(root.val)
            lis = lis + self.Inorder(root.right)
            
        return lis

    def find(self, target: int) -> bool:
        root = self.root
        lis = self.inorder
        lis.sort()
        
        return self.binarySearch (lis, 0, len(lis) -1, target)
    
    def binarySearch (self, lis: List[int], l: int, r: int, target: int) -> bool:
        if r>=l:
            mid = l+(r-l)//2
            if lis[mid] == target:
                return True
            elif lis[mid] > target:
                return self.binarySearch(lis, l, mid-1, target)
            else:
                return self.binarySearch(lis, mid+1, r, target)
        else:
            return False
        


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


# 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: TreeNode):
        root.val = 0
        nodes = [root]
        self.elements = [root.val]
        while nodes:
            node = nodes.pop(0)
            val = node.val
            if node.right is not None:
                self.elements.append(2 * val + 2)
                node.right.val = 2 * val + 2
                nodes.append(node.right)
            if node.left is not None:
                self.elements.append(2 * val + 1)
                node.left.val = 2 * val + 1
                nodes.append(node.left)

    def find(self, target: int) -> bool:
        try:
            value = self.elements.index(target)
            return True
        except ValueError:
            return False


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


# things learnt ..
# Try to check the first attempt and see if you can find the mistake
# we need a set or seen here .. 


# Second Attempt
class FindElements:
    
    def __init__(self, root: TreeNode):
        
        # fill using top down approach
        self.result = []
        q = []
        if root is None:
            return False
        q.append((root, 0))
        self.result.append(0)
        while len(q) > 0 :
            node, value = q.pop(0)
            #print(\" node \", node)
            #print(\"value is \", value)
            if node.left is not None:
                temp = (value*2) +1
                self.result.append(temp)
                q.append((node.left, temp))
                
                
            if node.right is not None:
                temp = (value*2) +2
                self.result.append(temp)
                q.append((node.right, temp))
        print((self.result))
#         def helper(root, value):
#             #base
            

            
            
#             if root.left is None and root.right is None:
#                 print(\"base case\")
#                 self.result.append(value)
#                 print(\"both null\")
#                 print(\"self.result \", self.result.copy())
#             #recursion
#             elif root.left is not None:
#                 self.result.append(value)
#                 temp = (value*2) +1
#                 helper(root.left, temp )
#                 print(\"left not null\")
#                 print(\"self.result \", self.result.copy())
#             elif root.right is not None:
#                 self.result.append(value)
#                 temp = (value*2) +2
#                 helper(root.right, temp )
#                 print(\"right not null\")
#                 print(\"self.result \", self.result.copy())
        
#         if root is None:
#             return False
#         helper(root, 0)
#         print(self.result)
#         return 
        
        

    def find(self, target: int) -> bool:
        return True if target in self.result else False
        
        




# 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


# first attempt
# below code almost looks ok , but it doesn't pass all test cases.

# class FindElements:
#     result = []
#     def __init__(self, root: TreeNode):
#         #result = []
        
#         # fill using top down approach
#         def helper(root, value):
#             #base
#             if root.left is None and root.right is None:
#                 self.result.append(value)
#             #recursion
#             elif root.left is not None:
#                 self.result.append(value)
#                 temp = (value*2) +1
#                 helper(root.left, temp )
#                 #print(\"left not null\")
#                 #print(\"self.result \", self.result)
#             elif root.right is not None:
#                 self.result.append(value)
#                 temp = (value*2) +2
#                 helper(root.right, temp )
#                 #print(\"right not null\")
#                 #print(\"self.result \", self.result)
        
#         if root is None:
#             return False
#         helper(root, 0)
#         print(self.result)
#         return 
        
        

#     def find(self, target: int) -> bool:
#         return True if target in self.result else False
        
        


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


# things learnt ..
# Try to check the first attempt and see if you can find the mistake
# we need a set or seen here .. 


# Second Attempt
class FindElements:
    
    def __init__(self, root: TreeNode):
        
        # fill using top down approach
        self.result = []
        q = []
        if root is None:
            return False
        q.append((root, 0))
        self.result.append(0)
        while len(q) > 0 :
            node, value = q.pop(0)
            #print(\" node \", node)
            #print(\"value is \", value)
            if node.left is not None:
                temp = (value*2) +1
                self.result.append(temp)
                q.append((node.left, temp))
                
                
            if node.right is not None:
                temp = (value*2) +2
                self.result.append(temp)
                q.append((node.right, temp))
        print((self.result))
        
    def find(self, target: int) -> bool:
        return True if target in self.result else False
        
        




# 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


# first attempt
# below code almost looks ok , but it doesn't pass all test cases.

# class FindElements:
#     result = []
#     def __init__(self, root: TreeNode):
#         #result = []
        
#         # fill using top down approach
#         def helper(root, value):
#             #base
#             if root.left is None and root.right is None:
#                 self.result.append(value)
#             #recursion
#             elif root.left is not None:
#                 self.result.append(value)
#                 temp = (value*2) +1
#                 helper(root.left, temp )
#                 #print(\"left not null\")
#                 #print(\"self.result \", self.result)
#             elif root.right is not None:
#                 self.result.append(value)
#                 temp = (value*2) +2
#                 helper(root.right, temp )
#                 #print(\"right not null\")
#                 #print(\"self.result \", self.result)
        
#         if root is None:
#             return False
#         helper(root, 0)
#         print(self.result)
#         return 
        
        

#     def find(self, target: int) -> bool:
#         return True if target in self.result else False
        
        


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


# 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 recoverTree(self, node: TreeNode) -> None: 
        if not node.left and not node.right:
            return None
        if node.left:
            node.left.val = 2 * node.val + 1
            self.num_set.add(node.left.val)
            self.recoverTree(node.left)
        if node.right:
            node.right.val = 2 * node.val + 2
            self.num_set.add(node.right.val)
            self.recoverTree(node.right)
        
    def __init__(self, root: TreeNode):
        root.val = 0
        self.num_set = set()
        self.num_set.add(0)
        self.recoverTree(root)
        self.root = root
        
        

    def find(self, target: int) -> bool:
        if target < self.root.val:
            return False
        return target in self.num_set


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


# 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: TreeNode):
        self.l=[0]
        self.root=root
        self.root.val=0
        d=deque()
        d.append(root)
        while d:
            x=d.popleft()
            if x.left:
                x.left.val=x.val*2+1
                d.append(x.left)
                self.l.append(x.left.val)
            if x.right:
                x.right.val=x.val*2+2
                d.append(x.right)
                self.l.append(x.right.val)
        

    def find(self, target: int) -> bool:
        return target in self.l


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


# 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: TreeNode):
        self.store = self.get_nodes(root)

    def get_nodes(self, root: TreeNode) -> list:
        result = []
        if root is not None:
            start = root
            start.val = 0
            seq = [start]
            while seq:
                store = []
                for i in seq:
                    result.append(i.val)
                    if i.left is not None:
                        left = i.left
                        left.val = i.val * 2 + 1
                        store.append(left)
                    if i.right is not None:
                        right = i.right
                        right.val = i.val * 2 + 2
                        store.append(right)
                seq = store
        return result

    def find(self, target: int) -> bool:
        if target in self.store:
            return True
        else:
            return False
        



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


# 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 rebuild(self,root:TreeNode):
        queue=[]
        root.val=0
        queue.append(root)
        while queue:
            new=queue.pop(0)
            if new.left:
                new.left.val=2*new.val+1
                self.collection.append(new.left.val)
                queue.append(new.left)
            if new.right:
                new.right.val=2*new.val+2
                self.collection.append(new.right.val)
                queue.append(new.right)

    def __init__(self, root: TreeNode):
        self.copy=root
        self.collection=[0]
        self.rebuild(self.copy)
        
        
    def find(self, target: int) -> bool:

        return target in self.collection
    



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


# 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):
        root.val = 0
        self.res = [0]
        
        def dfs(root):
            if root is None:
                return
            if root.left :
                root.left.val = 2*(root.val) + 1
                
                dfs(root.left)
            if root.right :
                root.right.val = 2*(root.val) + 2
                dfs(root.right)
            self.res.append(root.val)
        dfs(root)  
        
    def find(self, target):
        return target in self.res
        
        
        
        
        
        
        
        
        
        
        


# 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: TreeNode):
        self.root = root
        self.root.val = 0
        queue = []
        queue.append(root)
        self.values = []
        while(len(queue)>0):
            current = queue.pop(0)
            leftval = 2*current.val + 1
            rightval = 2*current.val + 2
            
            if(current.left is not None):
                current.left.val = leftval
                queue.append(current.left)
                self.values.append(current.left.val)
            if(current.right is not None):
                current.right.val = rightval
                queue.append(current.right)
                self.values.append(current.right.val)
            

    def find(self, target: int) -> bool:
        if (target in self.values):
            return True
      
            
                
            
                        


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


# 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: TreeNode):
        self.val_list = []
        def construct(node, val):
            if not node:
                return None
            node.val = val
            self.val_list.append(val)
            node.left = construct(node.left, 2*val+1)
            node.right = construct(node.right, 2*val+2)
            return node
        self.root = construct(root, 0)
        

    def find(self, target: int) -> bool:
        '''
        root = self.root
        def traverse(node):
            if not node:
                return False
            if node.val == target:
                return True
            elif target < node.val:
                return False
            else:
                return traverse(node.left) or traverse(node.right)
        return traverse(root)
        '''
        return target in self.val_list


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


# 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 dfs (self, root,x, Node_vals) : 
        
        if not root : 
            return  
        
        root.val = x 
        Node_vals.append (x)
        
        self.dfs (root.left , 2*x + 1,Node_vals)
        self.dfs (root.right, 2*x + 2, Node_vals)
        
        return Node_vals
    
    def __init__(self, root: TreeNode):
        self.N_V = self.dfs (root, 0, [])
        
    def find(self, target: int) -> bool:
        
        return target in self.N_V


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


# 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: TreeNode):
        self.val_list = []
        def construct(node, val):
            if not node:
                return None
            #node.val = val
            self.val_list.append(val)
            construct(node.left, 2*val+1)
            construct(node.right, 2*val+2)
            return node
        self.root = construct(root, 0)
        

    def find(self, target: int) -> bool:
        '''
        root = self.root
        def traverse(node):
            if not node:
                return False
            if node.val == target:
                return True
            elif target < node.val:
                return False
            else:
                return traverse(node.left) or traverse(node.right)
        return traverse(root)
        '''
        return target in self.val_list


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


# 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: TreeNode):
        self.values=[]
        self.tree=root
        
        def preorder(node, value):
            self.values.append(value)
            node.val=value
            if node.left:
                preorder(node.left, value*2+1)
            if node.right:
                preorder(node.right, value*2+2)
        
        preorder(root, 0)
        
        
    def find(self, target: int) -> bool:
        return target in self.values
                

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


# 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: TreeNode):
        self.root = root
        self.root.val = 0
        self.values = []
        self.__init(self.root)
        
    def __init(self, node):
        if node.left:
            value = 2 * node.val + 1
            node.left.val = value
            self.values.append(value)
            self.__init(node.left)
            
        if node.right:
            value = 2 * node.val + 2
            node.right.val = value
            self.values.append(value)
            self.__init(node.right)

            
    def __find(self, node, target) -> bool:
        if not node: 
            return False
        
        if node.val == target:
            return True
        
        return self.__find(node.left, target) \\
            or self.__find(node.right, target)
    
    def find(self, target: int) -> bool:
        return target in self.values
        # return self.__find(self.root, target)
        


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

# 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: TreeNode):
        
        self.d = collections.defaultdict(int)
        def recover(root,l,r,p):
            if not l and not r:
                root.val = 0
                
            elif r and not l:
                
                root.val = 2*p+2
            elif l and not r:
                root.val = 2*p+1
            self.d[root.val]+=1
            if root.left: root.left = recover(root.left, True, False, root.val)
            if root.right: root.right = recover(root.right, False, True, root.val)
            return root
        if root:
            node = recover(root, False,False, None)
        
                
            
            
            
        

    def find(self, target: int) -> bool:
        return (target in self.d)


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


# 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: TreeNode):
        self.elements = []
        def traverse(node,x):
            self.elements.append(x)
            if node.left != None:
                traverse(node.left,2*x+1)
            if node.right != None:
                traverse(node.right,2*x+2)
        traverse(root,0)
        

    def find(self, target: int) -> bool:
        return target in self.elements


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


# 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: TreeNode):
        self._all_vals = []
        def recover(root, val):
            root.val = val
            self._all_vals.append(val)
            if root.left:
                recover(root.left, 2*val+1)
            if root.right:
                recover(root.right, 2*val+2)
        recover(root, 0)
        self._root = root

    def find(self, target: int) -> bool:
        return target in self._all_vals            
        


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


# 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:
    treeroot = TreeNode()
    l = []
    def __init__(self, root: TreeNode):
        def correct(root):
            if root:
                if root.right:
                    root.right.val = 2*(root.val)+2
                    correct(root.right)
                if root.left:
                    root.left.val = 2*(root.val)+1
                    correct(root.left)
            return
        
        root.val = 0
        correct(root)
        self.treeroot = root
        self.l = self.inorder(self.treeroot)
    def inorder(self,root):
            if root:
                return self.inorder(root.left) + [root.val] + self.inorder(root.right)
            return []
    def find(self, target: int) -> bool:
        
        return (target in self.l)
        


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


# 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: TreeNode):
        self.tot_val = []
        def dfs(root, new_val):
            if not root:
                return
            root.val = new_val
            self.tot_val.append(new_val)
            if   root.left:
                dfs(root.left, new_val * 2+ 1)
            if   root.right:
                dfs(root.right, new_val * 2+ 2)    
        self.root = root
        dfs(self.root,0)
        

    def find(self, target: int) -> bool:
        if target in self.tot_val:
            return True
        else:
            return False


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


# 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: TreeNode):        
        self.m = []
        
        q = [root]
        root.val = 0
        while q:
            node = q.pop()
            if node.left: 
                node.left.val = 2*node.val+1
                self.m.append(node.left.val)
                q.append(node.left)
            if node.right:
                node.right.val = 2*node.val+2
                q.append(node.right)
                self.m.append(node.right.val)     

    def find(self, target: int) -> bool:
        return target in self.m
        


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


# 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: TreeNode):
        if not root:
            return root
        self.root = root
        self.root.val = 0
        self.vals = []
        self.vals.append(self.root.val)
        self.construct(self.root)
        print((self.vals))
        
        
    def construct(self, root):
        if root.left:
            root.left.val = 2*root.val + 1
            self.vals.append(root.left.val)
            self.construct(root.left)
        if root.right:
            root.right.val = 2*root.val + 2
            self.vals.append(root.right.val)
            self.construct(root.right)
        return root

    def find(self, target: int) -> bool:
        if target in self.vals:
            return True
        return False

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


# 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:
    rootNode = None
    elements = None
    def __init__(self, root: TreeNode):
        root.val = 0
        self.rootNode = root
        self.elements = []
        self.recover(self.rootNode)
        
    def recover(self, node):
        self.elements.append(node.val)
        if node.left!=None:
            node.left.val = 2*node.val+1
            self.recover(node.left)
        if node.right!=None:
            node.right.val = 2*node.val+2
            self.recover(node.right)


    def find(self, target: int) -> bool:
        return (target in self.elements)


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


# 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

def recover(root, nodes):
    nodes.append(root.val)
    if root.left:
        root.left.val = 2*(root.val) + 1
        recover(root.left, nodes)
    if root.right:
        root.right.val = 2*(root.val) + 2
        recover(root.right, nodes)
    
class FindElements:

    def __init__(self, root: TreeNode):
        root.val = 0
        nodes = []
        recover(root, nodes)
        self.tree = root
        self.nodes = nodes

    def find(self, target: int) -> bool:
        return target in self.nodes


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


# 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: TreeNode):
        self.root = root
        self.values = list()
        self.regen(root, 0)

    def find(self, target: int) -> bool:
        return target in self.values

    def regen(self, root, v):
        if root == None: return
        
        root.val = v
        self.values.append(v)
        
        self.regen(root.left, 2*v+1)
        self.regen(root.right, 2*v+2)
        
        


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


# 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:
    '''
    Algo:
    Iterate through the tree and restore the values of each node
    Add the node to a stack
        - with height of root
        - left or right info
            - left = 0, right = 1
            - (node, root_height, isRight)
    Iterate through the stack and calculate the value for the node
    using val = 2 * root_height + (1 + isRight)
    
    After nodes are fixed then iterate through the tree to find the node
    by adding all nodes to a stack
    '''

    def __init__(self, root: TreeNode):
        self.root = root
        node_list = []
        self.val_list = []
        if root:
            root.val = 0
            self.val_list.append(root.val)
            node_list.append((root.left, 0, 0))
            node_list.append((root.right, 0, 1))
            while len(node_list) > 0:
                cur_node, root_val, isRight = node_list.pop(-1)
                if cur_node:
                    print(f\"root_val: {root_val}, isRight: {isRight}\")
                    cur_node.val = 2 * root_val + (1 + isRight)
                    self.val_list.append(cur_node.val)
                    node_list.append((cur_node.left, cur_node.val,
                                     0))
                    node_list.append((cur_node.right, cur_node.val,
                                     1))
        

    def find(self, target: int) -> bool:
        # def dfs(node, val_list):
        #     if node:
        #         dfs(node.left, val_list)
        #         val_list.append(node.val)
        #         dfs(node.right, val_list)
        # val_list = []
        # dfs(self.root, val_list)
        # print(val_list)
        return target in self.val_list
                
        


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

# 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: TreeNode):
        self.root = root
        def recover(head, val):
            # if not head 比 if head is None 快
            # 在 TreeNode 下两者等价，但注意后者更规范
            # x = []
            # if not x      -- True
            # if x is None  -- False
            if not head:
                return
            head.val = val
            recover(head.left, val * 2 + 1)
            recover(head.right, val * 2 + 2)
        recover(root, 0)

    def find(self, target: int) -> bool:
        steps = bin(target + 1)[3:]
        head = self.root
        for s in steps:
            if not head:
                return False
            if s == '0':
                head = head.left
            else:
                head = head.right
        return head and head.val == target
        
            

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


# 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: TreeNode):
        self.all=[]
        def helperIter(root):
            val =0
            if not root:
                return
            
            stack = [(root, val)]
            while stack:
                curr, val = stack.pop()
                curr.val = val
                if curr.left:
                    self.all.append(2*val+1)
                    stack.append((curr.left, 2*val +1))
                if curr.right:
                    self.all.append(2*val +2)
                    stack.append((curr.right, 2*val +2))
            
        def helper(root, val):
            if not root:
                return

            if root:
                root.val= val
                self.all.append(val)
            
            if root.left:
                helper(root.left, 2*val +1)
            if root.right:
                helper(root.right, 2*val +2)
        
        # helper(root, 0)
        helperIter(root)
        
                    

    def find(self, target: int) -> bool:
        return target in self.all


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


# 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: TreeNode):
        self.q = []
        def search(node, value):
            if node:
                self.q.append(value)
                search(node.left, value*2 + 1)
                search(node.right, value*2 + 2)
        search(root,0)
        

    def find(self, target: int) -> bool:
        return target in self.q


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


# 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: TreeNode):
        self.allval = self._fix(root, 0)

    def find(self, target: int) -> bool:
        return target in self.allval
    
    def _fix(self, node, root_val):
        if node is None:
            return []
        
        node.val = root_val
        lv = self._fix(node.left, 2*root_val+1)
        rv = self._fix(node.right, 2*root_val+2)
        
        return [root_val] + lv + rv
        


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


# 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: TreeNode):
        self.root = root
        self.root.val = 0
        self.result = [0]
        self.dfs(self.root)
    def dfs(self,root):
        if not root:
            return
        if root.left:
            root.left.val = 2*root.val + 1
            self.result.append(root.left.val)
            self.dfs(root.left)
        if root.right:
            root.right.val = 2*root.val + 2
            self.result.append(root.right.val)
            self.dfs(root.right)

    def find(self, target: int) -> bool:
        return target in self.result
        


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


# 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:
    #list1=[]
    

    def __init__(self, root: TreeNode):
        root.val=0
        self.list1=[]
        self.helper(root)
        
    def helper(self,root):
        if not root:
            return
        self.list1.append(root.val)
        if root.left:
            root.left.val=2*root.val+1
            
        if root.right:
            root.right.val=2*root.val+2
           # print(self.list1)
        self.helper(root.left)
        self.helper(root.right)
   # print(\"list1\",list1)
    
        
    

    def find(self, target: int) -> bool:
        if target in self.list1:
            return True
        return False
        


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


# 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: TreeNode):
        stack=[root]
        root.val=0
        self.l=[]
        while stack:
            r=stack.pop()
            self.l.append(r.val)
            if r.left:
                stack.append(r.left)
                r.left.val=2*r.val+1
            if r.right:
                stack.append(r.right)
                r.right.val=2*r.val+2
        #print(self.l)
        

    def find(self, target: int) -> bool:
        return target in self.l
        


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


# 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: TreeNode):
        self.root = root
        self.vals = []
        self.createTree(root, 0)
    
    def createTree(self, root, val):
        root.val = val
        self.vals.append(val)
        if root.left is not None:
            self.createTree(root.left, 2*root.val+1)
            
        if root.right is not None:
            self.createTree(root.right, 2*root.val+2)
    
    def find(self, target: int) -> bool:
        return target in self.vals   
        #return self.findRec(target, self.root)
        
    def findRec(self, target, root):
        if root.val == target:
            #print(\"val\", root.val)
            #print(\"target\", target)
            #print(\"match\")
            return True
        if root.left is not None:     
            if self.findRec(target, root.left):
                #print(\"val\", root.val)
                #print(\"target\", target)
                #print(\"leftChildMatch\")
                return True
        if root.right is not None:
            if self.findRec(target, root.right):
                #print(\"val\", root.val)
                #print(\"target\", target)
                #print(\"rightChildMatch\")
                return True
        return False
    

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


# 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: TreeNode):
        self.data = []
        
        def walk(node, v):
            if(not node):
                return
            
            self.data.append(v)
            walk(node.left, 2*v+1)
            walk(node.right, 2*v+2)
        
        walk(root, 0)
        

    def find(self, target: int) -> bool:
        return target in self.data


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


# 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: TreeNode):
        def helper(root,val):
            if root is None:
                return 
            root.val=val
            helper(root.left,2*val+1)
            helper(root.right,2*val+2)
        helper(root,0)
        self.array=[]
        
        def help(root):
            if root is None:
                return
            help(root.left)
            self.array.append(root.val)
            help(root.right)
        help(root)   
        
        

    def find(self, target: int) -> bool:
        if target in self.array:
            return True
        return False
        


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


# 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, R: TreeNode):
        R.val, V = 0, set()
        def dfs(R):
            if R == None or R.left is R.right: return
            if R.left != None: R.left.val, _ = 2*R.val + 1, V.add(2*R.val + 1)
            if R.right != None: R.right.val, _ = 2*R.val + 2, V.add(2*R.val + 2)
            dfs(R.left), dfs(R.right)
        dfs(R)
        self.V = V
    def find(self, t: int) -> bool: return t in self.V



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


# 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: TreeNode):
        stack = [[root.left,1,0],[root.right,2,0]]
        self.ans = [0]
        while stack:
            x = stack.pop(0)
            if x[0] is not None:
                val = (x[2]*2) + x[1]
                self.ans.append(val)
                stack.append([x[0].left,1,val])
                stack.append([x[0].right,2,val])
        print((self.ans))

    def find(self, target: int) -> bool:
        return target in self.ans


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


# 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: TreeNode):
        
        self.val =  []
        root.val = 0 
        self.root = self.helper(root) #use dictionary to store vals
        
        
        
    def helper(self,root):
        if root:
            self.val.append(root.val)
            if root.left:
                root.left.val = 2 * root.val + 1
                l = self.helper(root.left)
            if root.right:
                root.right.val = 2 * root.val + 2
                r = self.helper(root.right)
            return root
        return 
        

    def find(self, target: int) -> bool:
        
        return target in self.val


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


# 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: TreeNode):
        
        self.ans = []
        
        def dfs(node,x):
            if not node:
                return
            
            node.val = x
            self.ans.append(x)
            dfs(node.left,2*x+1)
            dfs(node.right,2*x+2)
            
            return
        
        dfs(root,0)

    def find(self, target: int) -> bool:
        return target in self.ans


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


# 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: TreeNode):
        self.root=root
        self.root.val=0
        self.arr=[]
        self.fix(self.root)
        
    def fix(self,currentNode):
        self.arr.append(currentNode.val)
        if currentNode.left:
            
            currentNode.left.val=2*currentNode.val+1
            self.fix(currentNode.left)
        if currentNode.right:
            
            currentNode.right.val=2*currentNode.val+2
            self.fix(currentNode.right)
        
        

    def find(self, target: int) -> bool:
        
        if target in self.arr:
            return True
        else:
            return False
        
        


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


# 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: TreeNode):
        self.root = root
        root.val = 0
        self.nodes = []
        
        self.recoverTree(root, 0)
        
    def recoverTree(self, root, x):
        current = root
        
        if current:
            print((current.val, x))
            if current.val == x:
                self.nodes.append(current.val)
                if current.left:
                    current.left.val = 2 * x + 1
                    self.recoverTree(current.left, current.left.val)
                
                if current.right:
                    current.right.val = 2 * x + 2
                    self.recoverTree(current.right, current.right.val)
                    
    
    def find(self, target: int) -> bool:
        if target in self.nodes:
            return True
        
        else:
            return False
 


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


# 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: TreeNode):
        
        self.val =  []
        root.val = 0 
        self.root = self.helper(root)
        
        
        
    def helper(self,root):
        if root:
            self.val.append(root.val)
            if root.left:
                root.left.val = 2 * root.val + 1
                l = self.helper(root.left)
            if root.right:
                root.right.val = 2 * root.val + 2
                r = self.helper(root.right)
            return root
        return 
        

    def find(self, target: int) -> bool:
        
        return target in self.val
        # return self.helper2(self.root, target)
        
        
    '''def helper2(self, root, target):
        if root:
            if root.val == target:
                return True
            if root.val 
            l = self.helper2(root.left, target)
            r = self.helper2(root.right, target)
            return l or r  
        return False
    '''
        
        


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


# 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 recover(self, root):
        if not root:
            return 
        
        x = root.val
        
        if root.left:
            node_val = 2*x + 1
            root.left.val = node_val
            self.values.append(node_val)
            
        if root.right:
            node_val = 2*x + 2
            root.right.val = node_val
            self.values.append(node_val)
            
        self.recover(root.left)
        self.recover(root.right)
        
        return root
    
    def traverse(self,root):
        if not root:
            return 
        
        print((root.val))
        self.traverse(root.left)
        self.traverse(root.right)
        
    
    def __init__(self, root: TreeNode):
        root.val = 0
        self.values = [0]
        self.root = self.recover(root)
        
        
        
#     def find_target(self,target,root):
        
#         if not root:
#             return False
        
#         if root.val == target:
#             return True
        
#         else:
#             return self.find_target(target,root.left) or self.find_target(target,root.right)
        

    def find(self, target: int) -> bool:
        return target in self.values
        


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


# 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: TreeNode):
        
        self.arr = []
        def convert(curr):
            if curr:
                x = curr.val
                
                self.arr.append(x)
                if curr.left:
                    curr.left.val = 2 * x + 1
                if curr.right:
                    curr.right.val = 2 * x + 2
                
                convert(curr.left)
                convert(curr.right)
        
        root.val = 0
        convert(root)
        

    def find(self, target: int) -> bool:
        
        return target in self.arr


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


# 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: TreeNode):
        root.val = 0
        stack = [root]
        self.values = []
        
        while stack:
            cur = stack.pop()
                
            if cur.right:
                cur.right.val = cur.val * 2 + 2
                self.values.append(cur.right.val)
                stack.append(cur.right)

                
            if cur.left:
                cur.left.val = cur.val * 2 + 1
                self.values.append(cur.left.val)
                stack.append(cur.left)
        

    def find(self, target: int) -> bool:
        if target in self.values: return True
        return False


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


# 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: TreeNode):
        self.data = set()
        
        def walk(node, v):
            if(not node):
                return
            
            self.data.add(v)
            walk(node.left, 2*v+1)
            walk(node.right, 2*v+2)
        
        walk(root, 0)
        

    def find(self, target: int) -> bool:
        return target in self.data


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


# 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: TreeNode):
        root.val = 0
        self.recList = []
        self.recover(root)
        
    def recover(self, root):
        if root != None:
            self.recList.append(root.val)
            if root.left != None:
                root.left.val = 2*root.val +1
                self.recover(root.left)
            if root.right != None:
                root.right.val = 2*root.val +2
                self.recover(root.right)
            
    def find(self, target: int) -> bool:
        if target in self.recList:
            return True
        else:
            return False


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


# 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: TreeNode):
        
        root.val = 0
        self.vals = []
        
        def trav(node, prev, isLeft):
            if node.val != 0:
                if isLeft:
                    val = 2 * prev + 1
                    node.val = val
                    self.vals.append(val)
                else:
                    val = 2 * prev + 2
                    node.val = val
                    self.vals.append(val)
            if node.left:
                trav(node.left, node.val, True)
            if node.right:
                trav(node.right, node.val, False)
                    
        trav(root, 0, None)
        self.root = root
        

    def find(self, target: int) -> bool:
        
        return target in self.vals


# 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: TreeNode):
        self.tree = root
        self.values = []
        from collections import deque
        stack = deque()
        stack.append(root)
        root.val = 0
        curr = root
        while stack:
            if curr:
                self.values.append(curr.val)
                if curr.left:
                    curr.left.val = 2 * curr.val + 1
                if curr.right:
                    curr.right.val = 2 * curr.val + 2
                    stack.append(curr.right)
                curr = curr.left
            else:
                curr = stack.pop()

    def find(self, target: int) -> bool:
        if target in self.values:
            return True
        else:
            return False

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


# 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: TreeNode):
        
        self.values = []
        
        def evaluate(node, value):
            
            if not node:
                return
            
            node.val = value
            
            self.values.append(value)
            
            evaluate(node.left, value * 2 + 1) 
            evaluate(node.right, value * 2 + 2) 
        
        evaluate(root, 0)
        
    def find(self, target: int) -> bool:
        
        return target in self.values
        


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