Find Elements in a Contaminated Binary Tree - Video Solutions
Find Elements in a Contaminated Binary Tree | BFS | DFS | Leetcode 1261 | codestorywithMIK
Find Elements in a Contaminated Binary Tree - Video Solution
Watch 10 video solutions for Find Elements in a Contaminated Binary Tree, a medium level problem involving Hash Table, Tree, Depth-First Search. This walkthrough by codestorywithMIK has 7,457 views views. Want to try solving it yourself? Practice on FleetCode or read the detailed text solution.
Problem Statement
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.
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 |