Is Find Elements in a Contaminated Binary Tree easy or hard?

The problem is rated Medium because it combines binary tree traversal with a small design component. Understanding the value-generation formula is straightforward, but implementing efficient preprocessing and query handling requires familiarity with tree algorithms and hash sets.

Find Elements in a Contaminated Binary Tree Python/Java solution

Both Python and Java implementations reconstruct the tree and insert recovered values into a HashSet or set. The constructor performs DFS or BFS to compute node values, and the find(target) method simply checks whether the set contains the target.

How to solve Find Elements in a Contaminated Binary Tree in O(n)?

Traverse the contaminated tree once and reconstruct node values using the rules root=0, left=2x+1, and right=2x+2. Use DFS or BFS to visit each node and store the computed value in a hash set. After preprocessing, checking whether a target exists becomes a constant-time membership test.

What is the best approach for Find Elements in a Contaminated Binary Tree?

The best approach is to reconstruct the tree using DFS or BFS and store all recovered values in a hash set. Reconstruction takes O(n) time, and each find(target) query becomes an O(1) hash lookup. This design matches the expected solution pattern in interviews and coding platforms.

Is Find Elements in a Contaminated Binary Tree asked at Google/Amazon/Meta?

Tree reconstruction and design problems like this commonly appear in interviews at companies such as Amazon, Google, and Meta. Variations often test understanding of binary tree traversal, value propagation rules, and designing efficient query operations.

What data structure is used in Find Elements in a Contaminated Binary Tree?

The main data structures are a binary tree for reconstruction and a hash set for fast lookups. DFS uses recursion with the call stack, while BFS uses a queue to process nodes level by level. The hash set ensures O(1) average-time queries.

What is the time complexity of Find Elements in a Contaminated Binary Tree?

Recovering the entire tree requires visiting every node once, so preprocessing takes O(n) time. Each call to find(target) runs in O(1) time using a hash set lookup. The space complexity is O(n) for storing recovered values.

Description Hints 2 Solution Video 13:03

1261. Find Elements in a Contaminated Binary Tree

Medium84.1% acceptance2 companies

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.

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

Asked at 2 companies

Google Amazon

Topics

Hints open one at a time

Hint 1

Use DFS to traverse the binary tree and recover it.

Hint 2

Use a hashset to store TreeNode.val for finding.

13:03

Still stuck?Read 3 approaches, or watch a walkthrough.

Open solution

LanguageLoading editor…

1# Definition for a binary tree node.
2# class TreeNode:
3#     def __init__(self, val=0, left=None, right=None):
4#         self.val = val
5#         self.left = left
6#         self.right = right
7class FindElements:
8 
9    def __init__(self, root: Optional[TreeNode]):
10        
11 
12    def find(self, target: int) -> bool:
13        
14 
15 
16# Your FindElements object will be instantiated and called as such:
17# obj = FindElements(root)
18# param_1 = obj.find(target)

Starter codePython 3Spaces: 4

Examples

Case 1Case 2Case 3

Input

["FindElements","find","find"]
[[[-1,null,-1]],[1],[2]]

Input

["FindElements","find","find","find"]
[[[-1,-1,-1,-1,-1]],[1],[3],[5]]

Input

["FindElements","find","find","find","find"]
[[[-1,null,-1,-1,null,-1]],[2],[3],[4],[5]]

Your code is saved on this device.Solution