Find Elements in a Contaminated Binary Tree

Find Elements in a Contaminated Binary Tree

What is this problem about?

The Find Elements in a Contaminated Binary Tree interview question presents a unique tree recovery scenario. You are given a binary tree where all node values have been "contaminated" and changed to -1. The original tree followed a specific rule:

1. The root node value was 0.
2. If a node's value is x, its left child's value was 2x + 1 and its right child's value was 2x + 2. You need to design a class that "recovers" the tree upon initialization and provides a find method to check if a specific value exists in the recovered tree.

Why is this asked in interviews?

This Find Elements in a Contaminated Binary Tree coding problem is common at Amazon and Google because it tests your knowledge of Tree Traversal and System Design at a component level. It evaluations your ability to pre-process data to make future queries highly efficient. Interviewers want to see if you can trade initialization time and space for O(1) lookup performance.

Algorithmic pattern used

This problem uses the Breadth-First Search, Hash Table, Design, Binary Tree interview pattern. During the constructor call, you perform a traversal (either BFS or DFS) starting from the root. As you visit each node, you calculate its original value based on its parent's value and the given formula. To make the find operation fast, you store all these recovered values in a Hash Set.

Example explanation

Suppose the contaminated tree is a root with one left child.

1. Initialization:
   • Root starts at -1. We set it to 0 and add 0 to our Set.
   • Move to left child. Its parent has value 0. Formula: 2(0) + 1 = 1.
   • Set left child to 1 and add 1 to our Set.
2. Find(1): Check the Set. 1 exists. Return true.
3. Find(2): Check the Set. 2 does not exist. Return false.

Common mistakes candidates make

• Searching on Demand: Attempting to traverse the tree every time the find method is called. This leads to O(N) query time, which is inefficient compared to the O(1) Hash Set approach.
• Recursive Stack Overflow: Using DFS on a potentially very deep, skewed tree without considering stack limits (BFS is safer here).
• Missing the Set: Only recovering the tree structure but not storing values in a lookup-friendly format.

Interview preparation tip

Whenever you are asked to design a class where one method is called frequently (like find), focus on the Constructor. Use the constructor to "warm up" or pre-calculate all possible answers. This pattern is essential for high-performance applications.