Problem Description

You are given a binary tree that follows specific value assignment rules:

• The root node has value 0
• For any node with value x:
  • Its left child (if exists) has value 2 * x + 1
  • Its right child (if exists) has value 2 * x + 2

However, the tree has been contaminated - all node values have been changed to -1.

Your task is to implement a FindElements class with two methods:

1. Constructor FindElements(root): Takes the contaminated binary tree and recovers all node values according to the rules above.

2. Method find(target): Returns true if the target value exists in the recovered tree, false otherwise.

For example, if we have a tree structure:

       0
      / \
     1   2
    / \
   3   4

After contamination, all values become -1. The FindElements constructor should restore the original values based on the rules, and find(3) would return true while find(5) would return false.

The solution uses DFS to traverse the tree and restore values starting from the root (setting it to 0), then recursively calculates child values using the formulas 2 * x + 1 for left children and 2 * x + 2 for right children. All recovered values are stored in a hash set for O(1) lookup during find operations.

Flowchart Walkthrough

First, let's pin down the algorithm using the Flowchart. Here's a step-by-step walkthrough:

Is it a graph?

• Yes: A binary tree is a special type of graph where each node has at most two children and there are no cycles.

Is it a tree?

• Yes: The problem explicitly states we're working with a binary tree structure.

DFS

• We arrive at DFS: Since we're dealing with a tree structure, the flowchart directly leads us to use Depth-First Search.

Why DFS is appropriate for this problem:

• We need to traverse the entire tree to recover all node values from their contaminated state (-1)
• DFS allows us to process each node and recursively update its children's values based on the parent-child relationship (left child = 2parent + 1, right child = 2parent + 2)
• The recursive nature of DFS perfectly matches the recursive structure of the tree and the value assignment rules
• We can recover values in a single traversal, storing them in a hash set for O(1) lookup during find operations

Conclusion: The flowchart correctly identifies that for a tree-based problem like "Find Elements in a Contaminated Binary Tree," DFS is the optimal approach. The solution uses DFS to traverse from the root (setting it to 0), recursively calculate and assign values to children nodes, and store all recovered values in a set for efficient searching.

Intuition

The key insight is recognizing that even though all values are contaminated to -1, the tree structure itself remains intact. The parent-child relationships are preserved, which means we can reconstruct the original values by following the given rules.

Starting from what we know for certain - the root must be 0 - we can work our way down the tree. Once we know a parent's value, we can deterministically calculate its children's values using the formulas 2 * parent_value + 1 for the left child and 2 * parent_value + 2 for the right child.

This naturally suggests a traversal approach where we:

1. Fix the root value to 0
2. Visit each node and calculate its children's values based on the current node's value
3. Continue this process recursively through the entire tree

Since we need to check if values exist in the tree later, we should store all recovered values during our traversal. A hash set is perfect for this - it gives us O(1) lookup time for the find operation.

The beauty of this approach is that we only need to traverse the tree once during initialization to recover all values. After that, finding any target value becomes a simple set membership check. The contamination is just a distraction - the tree's structure tells us everything we need to know to restore the original values.

Learn more about Tree, Depth-First Search, Breadth-First Search and Binary Tree patterns.

Solution Approach

The implementation uses DFS with a hash table to efficiently recover and store all node values.

Data Structures Used:

• Set (self.s): Stores all recovered node values for O(1) lookup during find operations
• Tree traversal: Uses the existing tree structure to navigate through nodes

Implementation Details:

1. Constructor (__init__):

   • First, we manually set the root value to 0 since we know this is always the starting value
   • Initialize an empty set self.s to store all recovered values
   • Call the DFS helper function starting from the root

2. DFS Helper Function:

   • Add the current node's value to the set
   • If a left child exists:
     • Calculate its value as current_value * 2 + 1
     • Recursively process the left subtree
   • If a right child exists:
     • Calculate its value as current_value * 2 + 2
     • Recursively process the right subtree

3. Find Method:

   • Simply check if the target value exists in our set
   • Returns True if found, False otherwise

Why This Works:

• The DFS traversal ensures we visit every node exactly once
• As we traverse, we recover each node's value based on its parent's value
• By storing values in a set during traversal, we avoid the need to traverse the tree again for each find operation
• The in-place modification of node values means we're actually recovering the tree structure, not just collecting values

Time Complexity:

• Initialization: O(n) where n is the number of nodes (we visit each node once)
• Find operation: O(1) due to hash set lookup

Space Complexity:

• O(n) for storing all node values in the set
• O(h) for the recursion stack where h is the height of the tree

Example Walkthrough

Let's walk through a small contaminated tree to see how the solution recovers the values:

Initial contaminated tree:

       -1
      /  \
    -1    -1
    /
  -1

Step 1: Initialize FindElements

• Set root.val = 0 (we know root is always 0)
• Create empty set s = {}
• Start DFS from root

Step 2: DFS Traversal

Processing root (value = 0):

• Add 0 to set: s = {0}
• Root has left child, calculate: 2 * 0 + 1 = 1
• Set left child.val = 1
• Root has right child, calculate: 2 * 0 + 2 = 2
• Set right child.val = 2
• Recursively process children

Processing left child (value = 1):

• Add 1 to set: s = {0, 1}
• This node has left child, calculate: 2 * 1 + 1 = 3
• Set its left child.val = 3
• No right child, skip
• Recursively process left child

Processing node with value 3:

• Add 3 to set: s = {0, 1, 3}
• No children, return

Processing right child (value = 2):

• Add 2 to set: s = {0, 1, 2, 3}
• No children, return

Final recovered tree:

       0
      / \
     1   2
    /
   3

Step 3: Find operations

• find(1): Check if 1 in {0, 1, 2, 3} → returns True
• find(5): Check if 5 in {0, 1, 2, 3} → returns False
• find(0): Check if 0 in {0, 1, 2, 3} → returns True

The key insight is that we recover all values in one pass during initialization, then finding becomes a simple O(1) set lookup.

Solution Implementation

Time and Space Complexity

Time Complexity:

• Initialization (__init__): O(n) where n is the number of nodes in the binary tree. The dfs function visits each node exactly once to recover its value and add it to the set.
• Find operation (find): O(1) on average. Checking membership in a hash set is a constant-time operation.

Space Complexity:

• Overall: O(n) where n is the number of nodes in the binary tree.
  • The set self.s stores all n node values, requiring O(n) space.
  • The recursive dfs function uses the call stack, which in the worst case (a skewed tree) can go up to O(n) depth, requiring O(n) space.
  • In a balanced tree, the recursion depth would be O(log n), but we consider the worst case.

The algorithm recovers the values of a contaminated binary tree where the root should be 0, left children should be 2 * parent_val + 1, and right children should be 2 * parent_val + 2. It stores all recovered values in a set for efficient lookup during the find operation.

Learn more about how to find time and space complexity quickly.

Common Pitfalls

1. Forgetting to Handle the Root Node Separately

A common mistake is diving straight into the DFS without first setting the root value to 0. Since all nodes start with value -1, the recursive formula alone won't work correctly.

Incorrect approach:

def __init__(self, root):
    self.recovered_values = set()
    self.recover_tree(root)  # Root still has value -1!

Correct approach:

def __init__(self, root):
    root.val = 0  # Must set root value first
    self.recovered_values = set()
    self.recover_tree(root)

2. Using Wrong Formula for Child Values

It's easy to confuse the formulas or accidentally swap them. Remember:

• Left child: 2 * parent_val + 1
• Right child: 2 * parent_val + 2

Common mistakes:

# Wrong: Using same formula for both children
node.left.val = node.val * 2 + 1
node.right.val = node.val * 2 + 1  # Should be +2!

# Wrong: Swapping the formulas
node.left.val = node.val * 2 + 2   # Should be +1
node.right.val = node.val * 2 + 1  # Should be +2

3. Not Checking for Node Existence Before Access

Attempting to access or modify child nodes without checking if they exist will cause AttributeError.

Incorrect approach:

def recover_tree(node):
    self.recovered_values.add(node.val)
    node.left.val = node.val * 2 + 1  # Error if node.left is None!
    recover_tree(node.left)

Correct approach:

def recover_tree(node):
    self.recovered_values.add(node.val)
    if node.left:
        node.left.val = node.val * 2 + 1
        recover_tree(node.left)

4. Using List Instead of Set for Storage

Using a list for storing recovered values would make the find() operation O(n) instead of O(1).

Inefficient approach:

self.recovered_values = []  # O(n) lookup time
# ...
def find(self, target):
    return target in self.recovered_values  # Linear search

Efficient approach:

self.recovered_values = set()  # O(1) lookup time

5. Modifying Values After Adding to Set

Adding the node value to the set before recovering it (when it's still -1) would store incorrect values.

Incorrect order:

def recover_tree(node):
    self.recovered_values.add(node.val)  # Adding -1 for non-root nodes!
    if node.left:
        node.left.val = node.val * 2 + 1
        recover_tree(node.left)

Correct approach for non-root nodes: Set the value first, then add to set during recursion, or ensure root is handled before starting DFS.