Find Elements in a Contaminated Binary Tree

Problem Statement

You are given a contaminated binary tree where all TreeNode.val have been changed to -1. The tree follows these rules:

• The root node has a value of 0.
• If a node has a value x, then:
  • Its left child (if exists) will have a value 2 * x + 1.
  • Its right child (if exists) will have a value 2 * x + 2.

Task

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, otherwise returns false.

Test Case 1: Single Node Tree

Input

["FindElements","find","find"]
[[[-1]],[0],[1]]

Output

[null,true,false]

Explanation

FindElements findElements = new FindElements([-1]);
findElements.find(0); // returns True (root is always 0)
findElements.find(1); // returns False (no left or right child exists)

Test Case 2: Complete Binary Tree of Height 3

Input

["FindElements","find","find","find","find","find"]
[[[-1,-1,-1,-1,-1,-1,-1]],[3],[5],[6],[7],[8]]

Output

[null,true,true,true,false,false]

Explanation

FindElements findElements = new FindElements([-1,-1,-1,-1,-1,-1,-1]);
findElements.find(3); // returns True
findElements.find(5); // returns True
findElements.find(6); // returns True
findElements.find(7); // returns False (no node with value 7 exists)
findElements.find(8); // returns False (no node with value 8 exists)

Constraints

• $TreeNode.val = -1$
• The height of the binary tree is $\leq 20$.
• The total number of nodes is in the range $[1, 10^4]$.
• $find()$ will be called at most $10^4$ times.
• $0 \leq target \leq 10^6$.

Approach

1. Recover the tree using DFS or BFS:
   • Start from the root and assign it 0.
   • For each node x, assign its left child 2 * x + 1 and right child 2 * x + 2.
   • Store these values in a set or unordered_set for quick lookup.
2. Find operation in O(1):
   • Use a hash set to store valid node values for O(1) lookup in the find() function.