1261. Find Elements in a Contaminated Binary Tree

MediumTreeDepth-First SearchBreadth-First SearchDesignHash TableBinary 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 that root.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 supports O(1) average time complexity for search operations.
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 calls dfs on the left child.
  - If the current node has a right child, the right child's value is set using 2 * node.val + 2, and dfs is recursively called on the right child.
- This DFS algorithm continues until all nodes are visited and their values are corrected and stored.
Searching for a Target Value:
- The find function is straightforward. It simply checks if the target value is present in the self.vis set. If the target exists, it returns true; otherwise, it returns false.

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 Evaluator

Example 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   -1
/ 
-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.
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 be 2 * 0 + 1 = 1. So, our tree now looks like this:

Next, we move to the right child of the root (initially -1). The right child's value should be 2 * 0 + 2 = 2. Our tree becomes:

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 be 2 * 1 + 1 = 3. So, we recover this node, and the tree is fully recovered:

During the recovery, we add all the values 0, 1, 2, and 3 to the set self.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 with 3 as the parameter.
The find function checks whether 3 is in self.vis.
Since 3 is present in the set, the function returns true.

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.

Discover Your Strengths and Weaknesses: Take Our 2-Minute Quiz to Tailor Your Study Plan:

Question 1 out of 10

Is the following code DFS or BFS?

void search(Node root) {
  if (!root) return;
  visit(root);
  root.visited = true;
  for (Node node in root.adjacent) {
    if (!node.visited) {
      search(node);
    }
  }
}

Depth First Search

Breadth First Search

I don’t know