Find Elements in a Contaminated Binary Tree solution and explanation
Google
9 more videos on this problem
Find Elements in a Contaminated Binary Tree | BFS | DFS | Leetcode 1261 | codestorywithMIKcodestorywithMIK · 13:03 · 7K views
Find Elements in a Contaminated Binary Tree | Leetcode 1261Techdose · 10:20 · 3K views
Leetcode 1261: Find Elements in a Contaminated Binary TreeAlgorithms Casts · 9:48 · 947 views
Leetcode Solution - 1261 Find Elements in a Contaminated Binary TreeJohn Leonardo · 5:50 · 481 views
Daily Leetcode #1788: Feb 21, 2025 - 1261. Find Elements in a Contaminated Binary TreeProgramming Live with Larry · 6:01 · 398 views
Leetcode | 1261 Find Elements in a Contaminated Binary Tree | Java | Binary TreeCakot Coding · 7:25 · 343 views
1261. Find Elements in a Contaminated Binary Tree (Leetcode)App Fusion · 14:38 · 171 views
LeetCode 1261 Find Elements in a Contaminated Binary Tree | Design | Asked in Google AmazonCode Harmony · 17:08 · 132 views
Find Elements in a Contaminated Binary Tree - Leetcode 1261 | Using DFSCode With K5KC · 7:25 · 118 views
Leetcode 1261. Find Elements in a Contaminated Binary Tree (tree traveral)LetsCode · 6:29 · 61 views
The problem
Given a binary tree with the following rules:
root.val == 0- If
treeNode.val == xandtreeNode.left != null, thentreeNode.left.val == 2 * x + 1 - If
treeNode.val == xandtreeNode.right != null, thentreeNode.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)Returnstrueif thetargetvalue 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, 104] - Total calls of
find()is between[1, 104] 0 <= target <= 106
Approach overview
Problem Overview: You are given a binary tree where every node value has been contaminated and set to -1. The original tree followed a rule: the root was 0, the left child of value x was 2x + 1, and the right child was 2x + 2. Your task is to recover the tree and design a structure that efficiently checks whether a target value exists in it.
Approach 1: Recursive Tree Reconstruction (DFS) (Time: O(n), Space: O(n))
Start from the root and restore values using the rule that defines the original tree. Set the root to 0, then recursively assign 2x + 1 to the left child and 2x + 2 to the right child while traversing with Depth-First Search. During reconstruction, store every recovered value in a Hash Table or set. The find(target) operation becomes a constant-time lookup in the set. This approach is clean and natural because the recursive traversal mirrors the structure of the tree.
Approach 2: BFS Iterative Tree Recovery (Time: O(n), Space: O(n))
Instead of recursion, recover the tree level by level using a queue and Breadth-First Search. Initialize the root with value 0, push it into the queue, and iteratively process nodes while assigning values to children using the same formula. Each recovered value is inserted into a hash set for fast membership checks. BFS is useful if you want to avoid recursion depth limits or prefer an iterative traversal pattern when working with a Binary Tree.
Recommended for interviews: Recursive DFS reconstruction with a hash set is the most common solution. It clearly demonstrates understanding of tree traversal and the recovery formula while giving O(1) query time for find(). BFS is equally optimal but usually presented as an alternative implementation style.
Approach 1: Recursive Tree Reconstruction
This approach involves recursively traversing the contaminated binary tree and recovering the node values as per the given rules. As we traverse the tree, we will populate a set with the recovered values to allow efficient lookup for the find function.
class TreeNode:
def __init__(self, x):
self.val = x
self.left = None
self.right = None
class FindElements:
def __init__(self, root: TreeNode):
self.recovered = set()
self.recover(root, 0)
def recover(self, node, value):
if node is None:
return
node.val = value
self.recovered.add(value)
self.recover(node.left, 2 * value + 1)
self.recover(node.right, 2 * value + 2)
def find(self, target: int) -> bool:
return target in self.recoveredimport java.util.HashSet;
class TreeNode {
int val;
TreeNode left;
TreeNode right;
TreeNode(int x) { val = x; }
}
class FindElements {
private HashSet<Integer> recovered;
public FindElements(TreeNode root) {
recovered = new HashSet<>();
recover(root, 0);
}
private void recover(TreeNode node, int value) {
if (node == null) return;
node.val = value;
recovered.add(value);
recover(node.left, 2 * value + 1);
recover(node.right, 2 * value + 2);
}
public boolean find(int target) {
return recovered.contains(target);
}
}#include <unordered_set>
#include <queue>
using namespace std;
class TreeNode {
public:
int val;
TreeNode* left;
TreeNode* right;
TreeNode(int x) : val(x), left(NULL), right(NULL) {}
};
class FindElements {
private:
unordered_set<int> recovered;
void recover(TreeNode* node, int value) {
if (!node) return;
node->val = value;
recovered.insert(value);
if (node->left) recover(node->left, 2 * value + 1);
if (node->right) recover(node->right, 2 * value + 2);
}
public:
FindElements(TreeNode* root) {
recover(root, 0);
}
bool find(int target) {
return recovered.count(target) > 0;
}
};class TreeNode {
constructor(val, left = null, right = null) {
this.val = val;
this.left = left;
this.right = right;
}
}
class FindElements {
constructor(root) {
this.recovered = new Set();
this.recover(root, 0);
}
recover(node, value) {
if (!node) return;
node.val = value;
this.recovered.add(value);
this.recover(node.left, 2 * value + 1);
this.recover(node.right, 2 * value + 2);
}
find(target) {
return this.recovered.has(target);
}
}#include <stdbool.h>
#include <stdlib.h>
#include <stdio.h>
#include <string.h>
#include <assert.h>
typedef struct TreeNode {
int val;
struct TreeNode *left;
struct TreeNode *right;
} TreeNode;
typedef struct {
TreeNode *root;
bool *values;
} FindElements;
void recoverTree(TreeNode* node, int value, bool* values) {
if (node == NULL) return;
node->val = value;
values[value] = true;
if (node->left != NULL) recoverTree(node->left, 2 * value + 1, values);
if (node->right != NULL) recoverTree(node->right, 2 * value + 2, values);
}
FindElements* findElementsCreate(TreeNode* root) {
FindElements* obj = (FindElements*) malloc(sizeof(FindElements));
obj->root = root;
obj->values = (bool*) calloc(1000000, sizeof(bool));
recoverTree(root, 0, obj->values);
return obj;
}
bool findElementsFind(FindElements* obj, int target) {
return obj->values[target];
}
void findElementsFree(FindElements* obj) {
free(obj->values);
free(obj);
}using System.Collections.Generic;
public class TreeNode {
public int val;
public TreeNode left;
public TreeNode right;
public TreeNode(int val=0, TreeNode left=null, TreeNode right=null) {
this.val = val;
this.left = left;
this.right = right;
}
}
public class FindElements {
private HashSet<int> recovered;
public FindElements(TreeNode root) {
recovered = new HashSet<int>();
Recover(root, 0);
}
private void Recover(TreeNode node, int value) {
if (node == null) return;
node.val = value;
recovered.Add(value);
Recover(node.left, 2 * value + 1);
Recover(node.right, 2 * value + 2);
}
public bool Find(int target) {
return recovered.Contains(target);
}
}The Python solution uses a set to keep recovered node values. A recursive method recover pierces through the tree, assigning appropriate values, and storing them in the set. The constructor calls this recovery function, while the find method quickly checks set membership for the target.
Time Complexity: O(n) for recovery, O(1) for search.
Space Complexity: O(n) for storing the node values in a set.
Approach 2: BFS Iterative Tree Recovery
Utilizing a breadth-first search (BFS) strategy offers a way to recover and parse through the tree's nodes iteratively. Through this approach, we harness a queue to manage node processing, ensuring we systematically visit each node layer by layer.
from collections import deque
class TreeNode:
def __init__(self, x):
self.val = x
self.left = None
self.right = None
class FindElements:
def __init__(self, root: TreeNode):
self.recovered = set()
if root:
queue = deque([(root, 0)])
while queue:
node, value = queue.popleft()
node.val = value
self.recovered.add(value)
if node.left:
queue.append((node.left, 2 * value + 1))
if node.right:
queue.append((node.right, 2 * value + 2))
def find(self, target: int) -> bool:
return target in self.recoveredimport java.util.HashSet;
import java.util.LinkedList;
import java.util.Queue;
class TreeNode {
int val;
TreeNode left;
TreeNode right;
TreeNode(int x) { val = x; }
}
class FindElements {
private HashSet<Integer> recovered;
public FindElements(TreeNode root) {
recovered = new HashSet<>();
if (root != null) {
Queue<TreeNode> queue = new LinkedList<>();
Queue<Integer> valuesQueue = new LinkedList<>();
queue.add(root);
valuesQueue.add(0);
while (!queue.isEmpty()) {
TreeNode node = queue.poll();
int value = valuesQueue.poll();
node.val = value;
recovered.add(value);
if (node.left != null) {
queue.add(node.left);
valuesQueue.add(2 * value + 1);
}
if (node.right != null) {
queue.add(node.right);
valuesQueue.add(2 * value + 2);
}
}
}
}
public boolean find(int target) {
return recovered.contains(target);
}
}#include <unordered_set>
#include <queue>
using namespace std;
class TreeNode {
public:
int val;
TreeNode* left;
TreeNode* right;
TreeNode(int x) : val(x), left(NULL), right(NULL) {}
};
class FindElements {
private:
unordered_set<int> recovered;
public:
FindElements(TreeNode* root) {
if (root) {
queue<pair<TreeNode*, int>> q;
q.push({root, 0});
while (!q.empty()) {
auto [node, value] = q.front();
q.pop();
node->val = value;
recovered.insert(value);
if (node->left) q.push({node->left, 2 * value + 1});
if (node->right) q.push({node->right, 2 * value + 2});
}
}
}
bool find(int target) {
return recovered.count(target);
}
};class TreeNode {
constructor(val, left = null, right = null) {
this.val = val;
this.left = left;
this.right = right;
}
}
class FindElements {
constructor(root) {
this.recovered = new Set();
if (root) {
const queue = [{ node: root, value: 0 }];
while (queue.length > 0) {
const { node, value } = queue.shift();
node.val = value;
this.recovered.add(value);
if (node.left) queue.push({ node: node.left, value: 2 * value + 1 });
if (node.right) queue.push({ node: node.right, value: 2 * value + 2 });
}
}
}
find(target) {
return this.recovered.has(target);
}
}#include <stdbool.h>
#include <stdlib.h>
#include <stdio.h>
#include <string.h>
#include <assert.h>
typedef struct TreeNode {
int val;
struct TreeNode *left;
struct TreeNode *right;
} TreeNode;
typedef struct {
TreeNode *root;
bool *values;
} FindElements;
void bfsRecover(TreeNode* node, bool* values) {
if (node == NULL) return;
node->val = 0;
values[0] = true;
TreeNode* queue[10000];
int front = 0, rear = 0;
queue[rear++] = node;
while (front < rear) {
TreeNode* current = queue[front++];
if (current->left != NULL) {
current->left->val = 2 * current->val + 1;
values[current->left->val] = true;
queue[rear++] = current->left;
}
if (current->right != NULL) {
current->right->val = 2 * current->val + 2;
values[current->right->val] = true;
queue[rear++] = current->right;
}
}
}
FindElements* findElementsCreate(TreeNode* root) {
FindElements* obj = (FindElements*) malloc(sizeof(FindElements));
obj->root = root;
obj->values = (bool*) calloc(1000001, sizeof(bool));
bfsRecover(root, obj->values);
return obj;
}
bool findElementsFind(FindElements* obj, int target) {
return obj->values[target];
}
void findElementsFree(FindElements* obj) {
free(obj->values);
free(obj);
}using System.Collections.Generic;
public class TreeNode {
public int val;
public TreeNode left;
public TreeNode right;
public TreeNode(int x, TreeNode left = null, TreeNode right = null) {
this.val = x;
this.left = left;
this.right = right;
}
}
public class FindElements {
private HashSet<int> recovered;
public FindElements(TreeNode root) {
recovered = new HashSet<int>();
if (root != null) {
Queue<(TreeNode node, int value)> queue = new Queue<(TreeNode node, int value)>();
queue.Enqueue((root, 0));
while (queue.Count > 0) {
var (node, value) = queue.Dequeue();
node.val = value;
recovered.Add(value);
if (node.left != null) queue.Enqueue((node.left, 2 * value + 1));
if (node.right != null) queue.Enqueue((node.right, 2 * value + 2));
}
}
}
public bool Find(int target) {
return recovered.Contains(target);
}
}In Python, FindElements adopts BFS through a deque, where node and value pairs iterate over the tree. Data adheres to breadth-first order pairing, as node valuations align with principles found in the problem statement, and set ensures expedient access checks.
Time Complexity: O(n) stemming from exact node handling during the recovery phase.
Space Complexity: O(n) manifests from queue and set upkeep.
Approach 3: 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.
In terms of time complexity, it takes O(n) time to traverse the binary tree during initialization, and O(1) time to check if the target value exists in the hash table during search. The space complexity is O(n), where n is the number of nodes in the binary tree.
/**
* Definition for a binary tree node.
* class TreeNode {
* val: number
* left: TreeNode | null
* right: TreeNode | null
* constructor(val?: number, left?: TreeNode | null, right?: TreeNode | null) {
* this.val = (val===undefined ? 0 : val)
* this.left = (left===undefined ? null : left)
* this.right = (right===undefined ? null : right)
* }
* }
*/
class FindElements {
readonly #s = new Set<number>();
constructor(root: TreeNode | null) {
root.val = 0;
const dfs = (node: TreeNode | null, x = 0) => {
if (!node) return;
this.#s.add(x);
dfs(node.left, x * 2 + 1);
dfs(node.right, x * 2 + 2);
};
dfs(root);
}
find(target: number): boolean {
return this.#s.has(target);
}
}
/**
* Your FindElements object will be instantiated and called as such:
* var obj = new FindElements(root)
* var param_1 = obj.find(target)
*//**
* Definition for a binary tree node.
* type TreeNode struct {
* Val int
* Left *TreeNode
* Right *TreeNode
* }
*/
type FindElements struct {
s map[int]bool
}
func Constructor(root *TreeNode) FindElements {
root.Val = 0
s := map[int]bool{}
var dfs func(*TreeNode)
dfs = func(root *TreeNode) {
s[root.Val] = true
if root.Left != nil {
root.Left.Val = root.Val*2 + 1
dfs(root.Left)
}
if root.Right != nil {
root.Right.Val = root.Val*2 + 2
dfs(root.Right)
}
}
dfs(root)
return FindElements{s}
}
func (this *FindElements) Find(target int) bool {
return this.s[target]
}
/**
* Your FindElements object will be instantiated and called as such:
* obj := Constructor(root);
* param_1 := obj.Find(target);
*/Complexity comparison
| Approach | Complexity |
|---|---|
| Recursive Tree Reconstruction | Time Complexity: Space Complexity: |
| BFS Iterative Tree Recovery | Time Complexity: Space Complexity: |
| DFS + Hash Table | – |
Complexity analysis
| Approach | Time | Space | When to Use |
|---|---|---|---|
| Recursive Tree Reconstruction (DFS) | O(n) | O(n) | Clean implementation when recursion is acceptable and you want a straightforward recovery process |
| BFS Iterative Tree Recovery | O(n) | O(n) | Preferred when avoiding recursion or when implementing tree traversal iteratively |
Frequently asked questions
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.