How to Solve Find Elements in a Contaminated Binary Tree

This problem requires restoring a binary tree where all nodes are initially -1, applying DFS to reconstruct original values. Use a hash set to track recovered values for O(1) lookups during find operations. The main challenge is ensuring correct parent-child value reconstruction while maintaining efficient search performance.

Problem Statement

You are given a binary tree where every node's value has been changed to -1. The original tree followed the rules: the root had value 0, and for any node with value v, its left child had value 2v+1 and right child had value 2v+2. Implement a class that can recover the tree's original values and support querying whether a value exists.

Design the FindElements class with two operations: the constructor takes the contaminated tree and reconstructs all node values, and the find(target) method returns true if target exists in the recovered tree. Constraints: node values start at -1, tree height ≤ 20, total nodes 1 to 10^4, 0 ≤ target ≤ 10^6, and up to 10^4 find calls.

Examples

Example 1

Input: See original problem statement.

Output: See original problem statement.

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: See original problem statement.

Output: See original problem statement.

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: See original problem statement.

Output: See original problem statement.

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

Solution Approach

Depth-First Reconstruction

Use DFS to traverse the contaminated tree from the root, setting the root to 0, and recursively assign left and right children values based on 2v+1 and 2v+2 rules. This ensures all nodes are recovered correctly following the tree's original value pattern.

Hash Set Tracking

While traversing, insert each recovered value into a hash set. This allows find(target) queries to check existence in O(1) time, avoiding repeated traversal and ensuring fast lookups for large trees.

Handling Edge Cases

Account for null nodes during DFS to prevent errors. Ensure the hash set correctly stores all reachable nodes. Consider trees with missing children where child nodes might be null but the parent-child value formula still applies.

Complexity Analysis

Recovering the tree visits each node once using DFS, giving O(N) time. Storing all node values in a hash set uses O(N) space. Each find query is O(1) due to hash lookups.

What Interviewers Usually Probe

• Ask for reconstruction method and whether DFS or BFS is preferred.
• Check if candidate uses a hash set for fast find queries.
• Probe edge cases like missing left or right children and tree depth limits.

Common Pitfalls or Variants

Common pitfalls

• Failing to correctly compute child values from parent nodes, leading to incorrect tree reconstruction.
• Not handling null children and attempting to assign values, causing runtime errors.
• Using traversal without a hash set, resulting in O(N) find queries instead of O(1).

Follow-up variants

• Recovering a contaminated N-ary tree instead of a binary tree using similar value reconstruction rules.
• Supporting updates where new nodes are added to the recovered tree and find must reflect additions.
• Implementing the recovery with BFS instead of DFS to handle extremely wide trees more efficiently.

How GhostInterview Helps

• GhostInterview provides step-by-step DFS traversal reconstruction guidance to correctly assign node values.
• It suggests storing recovered values in a hash set for immediate existence queries during find operations.
• The solver highlights common edge cases and missing children scenarios, preventing runtime errors and ensuring correctness.

Topic Pages

• Hash Table
• Tree
• Depth-First Search
• Breadth-First Search
• Design
• Binary Tree

Related GhostInterview Pages

• LeetCode Interview Copilot - Use GhostInterview as a live solver when you want direct help with LeetCode-style coding questions.
• Coding Interview Assistant - See how GhostInterview supports array, string, linked list, graph, and tree interview workflows.
• How GhostInterview Works - Review the screenshot, reasoning, and answer flow before using the solver in a live interview.

FAQ

How do I reconstruct a contaminated binary tree for this problem?

Use DFS starting from the root set to 0, recursively assign left child as 2v+1 and right child as 2v+2, visiting all nodes.

Why is a hash set needed in FindElements?

A hash set stores all recovered node values, allowing O(1) lookups for the find(target) queries.

Can BFS be used instead of DFS?

Yes, BFS can reconstruct the tree level by level, but DFS is often simpler for recursive value assignment.

How to handle null children during reconstruction?

Check for null nodes before recursion to avoid runtime errors and ensure only existing children receive computed values.

Does this pattern apply to trees with arbitrary missing nodes?

Yes, the parent-child value formula still works, but only assign values to existing nodes and skip null children.