# Solving Leetcode Interviews in Seconds with AI: Find Elements in a Contaminated Binary Tree


	# Introduction
	In this blog post, we will explore how to solve the LeetCode problem "1261" using AI. LeetCode is a popular platform for preparing for coding interviews, and with the help of AI tools like [Chatmagic](https://www.chatmagic.app), we can generate solutions quickly and efficiently - helping you pass the interviews and get the job offer without having to study for months.

	# Problem Statement
	> Given a binary tree with the following rules:  root.val == 0 For any treeNode: 	 If treeNode.val has a value x and treeNode.left != null, then treeNode.left.val == 2 * x + 1 If treeNode.val has a value x and treeNode.right != null, then treeNode.right.val == 2 * x + 2    Now the binary tree is contaminated, which means all treeNode.val have been changed to -1. Implement the FindElements class:  FindElements(TreeNode* root) Initializes the object with a contaminated binary tree and recovers it. bool find(int target) Returns true if the target value exists in the recovered binary tree.    Example 1:   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, 104] Total calls of find() is between [1, 104] 0 <= target <= 106  

	# Explanation
	Here's a breakdown of the solution and the Python code:

*   **High-Level Approach:**
    *   **Reconstruct the Tree:** During initialization, perform a Depth-First Search (DFS) or Breadth-First Search (BFS) to correct the values of the tree nodes, starting from the root (value 0).
    *   **Store Values in a Set:** As the tree is corrected, store the valid node values in a set data structure. This allows for very efficient `find` operations.
    *   **Efficient Search:** The `find` operation simply checks if the target value is present in the set.

*   **Complexity:**
    *   **Time Complexity:** O(N) for initialization, where N is the number of nodes in the tree. O(1) for the `find` operation.
    *   **Space Complexity:** O(N) to store the set of node values in the worst case.

	
	# Code
	```python
	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()
        self.recover_tree(root, 0)

    def recover_tree(self, node: TreeNode, val: int):
        if not node:
            return

        node.val = val
        self.values.add(val)

        if node.left:
            self.recover_tree(node.left, 2 * val + 1)
        if node.right:
            self.recover_tree(node.right, 2 * val + 2)

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