1261. Find Elements in a Contaminated Binary Tree
Problem Description
The problem presents a unique type of binary tree structure where the value of each node can be determined by its parent node's value using specific rules. For a node with value 'x', if it has a left child, the left child's value would be 2 * x + 1
, and if it has a right child, the right child's value would be 2 * x + 2
. However, there is a twist: the binary tree is contaminated, meaning all node values are converted to -1
. The FindElements
class is designed to recover such a tree and perform searches for values after its recovery.
Flowchart Walkthrough
First, let's analyze the problem using the Flowchart. Here's a step-by-step walkthrough:
Is it a graph?
- Yes: The binary tree can be treated as a graph where nodes are connected with edges following the parent-child relationship.
Is it a tree?
- Yes: Given that the structure involved is specifically referred to as a binary tree, it follows that it is indeed a tree.
Does the problem involve using Depth-First Search (DFS)?
Since the flowchart points directly from identifying the structure as a tree to applying DFS, we can conclude that Depth-First Search (DFS) is an appropriate method to traverse or modify the tree in a way that suits the solution for the problem of recovering a binary tree that has been modified. DFS is efficient for tree explorations and manipulations, allowing selective access and operations on various nodes, which is suitable for the Find Elements operation in a contaminated binary tree.
Conclusion: The flowchart suggests using DFS for this problem, as it involves operations on a tree structure, making DFS an ideal choice for efficiently exploring and modifying nodes according to the given conditions in the problem.
Intuition
The intuitive approach to solve this problem involves two phases: recovery and search. In the recovery phase, we need to reinstate each node's value based on the rules mentioned in the problem description. We start at the root node, which is set to 0, and traverse the tree using depth-first search (DFS). While traversing, we correct the value of each node according to its position (whether it's a left or right child) using the given formulas.
Once the values are recovered and set, we store them in a set during the traversal. This allows us to later check if a target value exists efficiently. The recovery process ensures that all values in the tree are unique, thus a set is the perfect data structure for quick lookup operations.
The search phase is quite simple. Since we've stored recovered values in a set, finding a target value is now a matter of checking its presence in the set, which is a constant time operation.
Learn more about Tree, Depth-First Search, Breadth-First Search and Binary Tree patterns.
Solution Approach
To implement the solution, we utilize a depth-first search (DFS) algorithm starting from the root of the tree. DFS is a tree traversal technique that starts at the root node and explores as far as possible along each branch before backtracking. The algorithm has been slightly modified to recover and store the values of each node during traversal.
Here's a breakdown of how the algorithm works in the given solution:
-
Initialization:
- We override the root value to
0
since it's given thatroot.val == 0
when the tree is not contaminated. - A set named
self.vis
is initialized to keep track of all the recovered values in the tree. The set is chosen because it supportsO(1)
average time complexity for search operations.
- We override the root value to
-
DFS Traversal and Recovery:
- We define a helper function
dfs
, which takes a node as an argument and performs the following operations:- It first adds the current node's value to the set
self.vis
. - If the current node has a left child, it calculates the left child's value using the formula
2 * node.val + 1
and then recursively callsdfs
on the left child. - If the current node has a right child, the right child's value is set using
2 * node.val + 2
, anddfs
is recursively called on the right child.
- It first adds the current node's value to the set
- This DFS algorithm continues until all nodes are visited and their values are corrected and stored.
- We define a helper function
-
Searching for a Target Value:
- The
find
function is straightforward. It simply checks if the target value is present in theself.vis
set. If the target exists, it returnstrue
; otherwise, it returnsfalse
.
- The
The choice of using DFS for recovery ensures that all nodes are visited and corrected according to their intended values. The recovery process is one-time during the object's initialization, which makes subsequent search operations very efficient due to the constant lookup time in the set.
Ready to land your dream job?
Unlock your dream job with a 2-minute evaluator for a personalized learning plan!
Start EvaluatorExample Walkthrough
Let's illustrate the solution approach with a simple example. Suppose we have a contaminated binary tree with all nodes having a value of -1
, and the structure of the tree is as follows:
1 -1 2 / \ 3 -1 -1 4/ 5-1
Upon initializing our FindElements
class with this tree, we want to recover it. The recovery process will proceed as follows:
-
Initial Recovery:
- We start with the root node and override its value to
0
.
- We start with the root node and override its value to
-
First Level of Recovery:
- We move to the left child of the root (initially
-1
). According to our formula, the left child's value should be2 * 0 + 1 = 1
. So, our tree now looks like this:
- We move to the left child of the root (initially
1 0 2 / \ 3 1 -1 4 / 5-1
- Next, we move to the right child of the root (initially
-1
). The right child's value should be2 * 0 + 2 = 2
. Our tree becomes:
1 0 2 / \ 3 1 2 4 / 5-1
- Second Level of Recovery:
- There's one more node left, which is the left child of node
1
. According to our formula, this node's value should be2 * 1 + 1 = 3
. So, we recover this node, and the tree is fully recovered:
- There's one more node left, which is the left child of node
1 0 2 / \ 3 1 2 4 / 53
- During the recovery, we add all the values
0
,1
,2
, and3
to the setself.vis
.
Now the tree is recovered, and our set self.vis
contains {0, 1, 2, 3}
.
For the search phase, let's say we want to find the value 3
:
- We call the
find
function with3
as the parameter. - The
find
function checks whether3
is inself.vis
. - Since
3
is present in the set, the function returnstrue
.
Alternatively, if we were searching for a non-existent value like 5
, the find
function would check for 5
in the set, not find it, and return false
.
The above walkthrough provides a concrete example of how the described algorithm recovers a contaminated tree and facilitates fast searches for values post-recovery.
Solution Implementation
1# Definition for a binary tree node.
2class TreeNode:
3 def __init__(self, val=0, left=None, right=None):
4 self.val = val
5 self.left = left
6 self.right = right
7
8class FindElements:
9 def __init__(self, root: Optional[TreeNode]):
10 # Helper function to recover the tree
11 def recover_tree(node):
12 # Add the current node's value to the visited set
13 self.visited.add(node.val)
14 # If the left child exists, set its value and recover the left subtree
15 if node.left:
16 node.left.val = node.val * 2 + 1
17 recover_tree(node.left)
18 # If the right child exists, set its value and recover the right subtree
19 if node.right:
20 node.right.val = node.val * 2 + 2
21 recover_tree(node.right)
22
23 # Initialize the root value to 0
24 root.val = 0
25 # Create a set to keep track of all values in the recovered tree
26 self.visited = set()
27 # Start the tree recovery process
28 recover_tree(root)
29
30 def find(self, target: int) -> bool:
31 # Check if the target is in the visited set
32 return target in self.visited
33
34
35# Your FindElements object will be instantiated and called as such:
36# obj = FindElements(root)
37# param_1 = obj.find(target)
38
1import java.util.HashSet;
2import java.util.Set;
3
4// Reconstructed tree where every node's value equals twice the value of their
5// parent (left child) or twice the value plus one (right child), as if it were
6// a binary heap, starting with 0 as the root's value.
7class FindElements {
8 // Store the values of all the nodes after "recovering" the tree
9 private Set<Integer> recoveredValues = new HashSet<>();
10
11 // Constructor that starts the recovery process of the given tree
12 public FindElements(TreeNode root) {
13 if (root == null) {
14 return;
15 }
16 root.val = 0; // The recovery process starts by setting the root's value to 0
17 recoverTree(root);
18 }
19
20 // Helper method to recover the tree
21 private void recoverTree(TreeNode node) {
22 if (node == null) {
23 return;
24 }
25 recoveredValues.add(node.val); // Add the current node's value to the set
26 // Recursively recover the left subtree, if it exists, by setting the left child's value
27 if (node.left != null) {
28 node.left.val = 2 * node.val + 1;
29 recoverTree(node.left);
30 }
31 // Recursively recover the right subtree, if it exists, by setting the right child's value
32 if (node.right != null) {
33 node.right.val = 2 * node.val + 2;
34 recoverTree(node.right);
35 }
36 }
37
38 // Check if a target value exists in the recovered tree
39 public boolean find(int target) {
40 return recoveredValues.contains(target);
41 }
42}
43
44/**
45 * This class can be used as shown below:
46 * FindElements findElements = new FindElements(root);
47 * boolean isFound = findElements.find(target);
48 */
49
1#include <functional>
2#include <unordered_set>
3
4// Definition for a binary tree node.
5struct TreeNode {
6 int val;
7 TreeNode *left;
8 TreeNode *right;
9 TreeNode() : val(0), left(nullptr), right(nullptr) {}
10 TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
11 TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}
12};
13
14class FindElements {
15public:
16 // Constructor: Recovers a tree with values changed by the constructor.
17 explicit FindElements(TreeNode* root) {
18 // Start by setting the root value to 0, as per the problem statement.
19 root->val = 0;
20 // Depth-first search (DFS) to recover the tree.
21 std::function<void(TreeNode*)> recoverTree = [&](TreeNode* node) {
22 // Store the recovered value in the hash set.
23 recoveredValues.insert(node->val);
24
25 // If the left child exists, set its value and recover its subtree.
26 if (node->left) {
27 node->left->val = node->val * 2 + 1;
28 recoverTree(node->left);
29 }
30
31 // If the right child exists, set its value and recover its subtree.
32 if (node->right) {
33 node->right->val = node->val * 2 + 2;
34 recoverTree(node->right);
35 }
36 };
37
38 // Start recovering the tree from the root.
39 recoverTree(root);
40 }
41
42 // Checks if a value exists in the recovered tree.
43 bool find(int target) {
44 // Return true if the target value is in the hash set, false otherwise.
45 return recoveredValues.count(target) > 0;
46 }
47
48private:
49 std::unordered_set<int> recoveredValues; // Stores the recovered values in the tree.
50};
51
52// Usage example:
53// TreeNode* root; // Assume root is a pointer to the TreeNode structure that represents the corrupted tree.
54// FindElements* findElements = new FindElements(root);
55// bool isFound = findElements->find(target); // Replace 'target' with the value you want to find.
56
1// Type definition for a binary tree node.
2class TreeNode {
3 val: number;
4 left: TreeNode | null;
5 right: TreeNode | null;
6
7 constructor(val: number = 0, left: TreeNode | null = null, right: TreeNode | null = null) {
8 this.val = val;
9 this.left = left;
10 this.right = right;
11 }
12}
13
14// Set to store the recovered values in the tree.
15const recoveredValues = new Set<number>();
16
17// Helper function to recover the tree.
18function recoverTree(node: TreeNode): void {
19 // Store the recovered value in the set.
20 recoveredValues.add(node.val);
21
22 // If the left child exists, set its value and recover its subtree.
23 if (node.left) {
24 node.left.val = node.val * 2 + 1;
25 recoverTree(node.left);
26 }
27
28 // If the right child exists, set its value and recover its subtree.
29 if (node.right) {
30 node.right.val = node.val * 2 + 2;
31 recoverTree(node.right);
32 }
33}
34
35// Recovery function to initialize and restore the tree based on root.
36function initializeRecovery(root: TreeNode): void {
37 // Start by setting the root value to 0, as per the problem statement.
38 root.val = 0;
39 // Start recovering the tree from the root.
40 recoverTree(root);
41}
42
43// Function to check if a value exists in the recovered tree.
44function find(target: number): boolean {
45 // Return true if the target value is in the set, false otherwise.
46 return recoveredValues.has(target);
47}
48```
49
50Here's how you can use the provided functions:
51
52```typescript
53let root = new TreeNode(); // Assume 'root' is an instance of TreeNode, representing the corrupted tree.
54initializeRecovery(root); // Initialize recovery with 'root', which recovers the tree's values.
55let isFound = find(target); // Replace 'target' with a numerical value you wish to find in the recovered tree.
56
Time and Space Complexity
Time Complexity
The __init__
method of the FindElements
class has a time complexity of O(n)
, where n
is the number of nodes in the tree. This is because it performs a Depth-First Search (DFS) on the tree, visiting each node exactly once to recover the original values assuming the tree was distorted by having every node's value changed to -1
. During this traversal, each node's value is updated based on its parent's value, and the value is added to the vis
(visited) set.
The find
method has a time complexity of O(1)
, as it is a simple lookup operation in a set to check for the presence of the target
value.
Space Complexity
The space complexity of the FindElements
class is O(n)
, because it stores each node's value in a set vis
. The size of this set is directly proportional to the number of nodes in the tree.
In summary, the DFS in the constructor (__init__
) dominates the time complexity, making it O(n)
, while the space complexity is also O(n)
due to the storage required for the vis
set.
Learn more about how to find time and space complexity quickly using problem constraints.
Which of the following uses divide and conquer strategy?
Recommended Readings
Everything About Trees A tree is a type of graph data structure composed of nodes and edges Its main properties are It is acyclic doesn't contain any cycles There exists a path from the root to any node Has N 1 edges where N is the number of nodes in the tree and
https algomonster s3 us east 2 amazonaws com cover_photos dfs svg Depth First Search Prereqs Recursion Review problems recursion_intro Trees problems tree_intro With a solid understanding of recursion under our belts we are now ready to tackle one of the most useful techniques in coding interviews Depth First Search DFS
https algomonster s3 us east 2 amazonaws com cover_photos bfs svg Breadth First Search on Trees Hopefully by this time you've drunk enough DFS Kool Aid to understand its immense power and seen enough visualization to create a call stack in your mind Now let me introduce the companion spell
Got a question? Ask the Monster Assistant anything you don't understand.
Still not clear?  Submit the part you don't understand to our editors. Or join our Discord and ask the community.