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

Source: leetcode | Difficulty: MEDIUM
Tags: Tree algorithms

Data structures

Graph traversal

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


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]:
	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:
		self.tree.val = 0
		p = get_path(target)
		return find(self.tree, p)


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


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


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


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)


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


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


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


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


class FindElements:

	def __init__(self, root: TreeNode):
		self.root = root
		self.container = set()

		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)
		return

	def find(self, target: int) -> bool:

		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
				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)
		return trav(self.root, 0, path)


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


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


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


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


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)


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
					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


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]:
			k = s & 1 << c - 1
			if k:
				if node.right:
					node = node.right
				else:
					return False
			elif node.left:
				node = node.left
			else:
				return False
		return node and node.val == s - 1


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)

	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


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


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


class FindElements:

	def __init__(self, root: TreeNode):
		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)
			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


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


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


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


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


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


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:
		return target in self.val_list


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


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


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


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


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


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


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


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


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


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


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


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)


class FindElements:

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

		def recover(head, val):
			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


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)
		helperIter(root)

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


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


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


class FindElements:

	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
		self.helper(root.left)
		self.helper(root.right)

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


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

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


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

	def findRec(self, target, root):
		if root.val == target:
			return True
		if root.left is not None:
			if self.findRec(target, root.left):
				return True
		if root.right is not None:
			if self.findRec(target, root.right):
				return True
		return False


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


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


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


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


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


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(self, target: int) -> bool:
		return target in self.values


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


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


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


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


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