#1261

Medium

auto_awesomeBinary-tree traversal and state tracking

LeetCode Problem Workspace

Find Elements in a Contaminated Binary Tree

Recover values in a contaminated binary tree and efficiently check for existence using traversal and state tracking techniques.

hash table tree depth first search breadth first search design

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 2 v+1 and right child had value 2 v+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 2 v+1 and 2 v+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

Metric	Value
Time	O(N)
Space	O(N)

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.

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 2 v+1 and right child as 2 v+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.

terminal

Solution

Solution 1: DFS + Hash Table

First, we traverse the binary tree using DFS, restore the node values to their original values, and store all node values in a hash table. Then, when searching, we only need to check if the target value exists in the hash table.

1

2

3

4

5

6

7

8

9

10

11

12

13

14

15

16

17

18

19

20

21

22

23

24

25

26

27

28

29

# Definition for a binary tree node.
# 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: Optional[TreeNode]):
        def dfs(root: Optional[TreeNode]):
            self.s.add(root.val)
            if root.left:
                root.left.val = root.val * 2 + 1
                dfs(root.left)
            if root.right:
                root.right.val = root.val * 2 + 2
                dfs(root.right)

        root.val = 0
        self.s = set()
        dfs(root)

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


# Your FindElements object will be instantiated and called as such:
# obj = FindElements(root)
# param_1 = obj.find(target)

Continue Practicing

#1123 lowest common ancestor of deepest leaves #987 vertical order traversal of a binary tree #865 smallest subtree with all the deepest nodes