Problem Description

You are given a binary tree where all the node values have been contaminated and set to -1. The original binary tree satisfied the following rules:

• The root node had a value of 0.
• For any node with value x:
  • If the node has a left child, its value is 2 * x + 1.
  • If the node has a right child, its value is 2 * x + 2.

Your tasks are:

1. Recover the original values of the tree by following the rules above.
2. Implement a find function that returns true if a given target value exists in the tree, and false otherwise.

• There is only one valid way to recover the tree values.
• Node values are unique and non-negative after recovery.
• The find function may be called many times.

Thought Process

The key to this problem is understanding how to reconstruct the original values of the binary tree. Since all nodes initially have the value -1, we must traverse the tree and assign the correct values based on their position and the rules provided.

A brute-force approach would be to reconstruct the value of each node on-the-fly during every find call, but this would be inefficient, especially if find is called multiple times.

To optimize, we can recover the tree once (at initialization) and store all valid node values in a fast-access data structure (like a hash set). This way, every find operation becomes a simple and efficient lookup.

Solution Approach

Here’s how we can efficiently solve the problem:

1. Recover the Tree:
   • Start by setting the root node's value to 0.
   • Recursively traverse the tree using DFS (Depth-First Search).
   • For each node, assign its left child the value 2 * parent + 1 and its right child 2 * parent + 2 (if they exist).
2. Store Values:
   • As we recover each node, store its value in a hash set. This allows us to check if a value exists in O(1) time.
3. Implement Find:
   • In the find method, simply check if the target value is in the hash set.

This approach ensures that tree recovery is done only once, and all subsequent find calls are extremely fast.

Example Walkthrough

Suppose the contaminated tree structure is:

        -1
       /  \
     -1   -1
    /
  -1
  

Step-by-step recovery:

1. Set root value to 0.
2. Root's left child: 2*0+1 = 1
3. Root's right child: 2*0+2 = 2
4. Left child's left child: 2*1+1 = 3

The recovered values are: 0, 1, 2, 3

Sample find calls:

• find(1) returns true (since 1 exists)
• find(4) returns false (since 4 doesn't exist)

Code Implementation

# Definition for a binary tree node.
# class TreeNode:
#     def __init__(self, val=0, left=None, right=None):
#         self.val = val
#         self.left = left
#         self.right = right

class FindElements:
    def __init__(self, root: TreeNode):
        self.values = set()
        def recover(node, val):
            if not node:
                return
            node.val = val
            self.values.add(val)
            recover(node.left, 2 * val + 1)
            recover(node.right, 2 * val + 2)
        recover(root, 0)

    def find(self, target: int) -> bool:
        return target in self.values
      

/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode() : val(0), left(nullptr), right(nullptr) {}
 *     TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
 *     TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}
 * };
 */
class FindElements {
    unordered_set<int> values;
    void recover(TreeNode* node, int val) {
        if (!node) return;
        node->val = val;
        values.insert(val);
        recover(node->left, 2 * val + 1);
        recover(node->right, 2 * val + 2);
    }
public:
    FindElements(TreeNode* root) {
        recover(root, 0);
    }
    
    bool find(int target) {
        return values.count(target) > 0;
    }
};
      

/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode() {}
 *     TreeNode(int val) { this.val = val; }
 *     TreeNode(int val, TreeNode left, TreeNode right) {
 *         this.val = val;
 *         this.left = left;
 *         this.right = right;
 *     }
 * }
 */
import java.util.HashSet;
import java.util.Set;

class FindElements {
    private Set<Integer> values = new HashSet<>();

    public FindElements(TreeNode root) {
        recover(root, 0);
    }
    
    private void recover(TreeNode node, int val) {
        if (node == null) return;
        node.val = val;
        values.add(val);
        recover(node.left, 2 * val + 1);
        recover(node.right, 2 * val + 2);
    }
    
    public boolean find(int target) {
        return values.contains(target);
    }
}
      

/**
 * Definition for a binary tree node.
 * function TreeNode(val, left, right) {
 *     this.val = (val===undefined ? 0 : val)
 *     this.left = (left===undefined ? null : left)
 *     this.right = (right===undefined ? null : right)
 * }
 */

var FindElements = function(root) {
    this.values = new Set();
    const recover = (node, val) => {
        if (!node) return;
        node.val = val;
        this.values.add(val);
        recover(node.left, 2 * val + 1);
        recover(node.right, 2 * val + 2);
    }
    recover(root, 0);
};

FindElements.prototype.find = function(target) {
    return this.values.has(target);
};
      

Time and Space Complexity

• Brute-force approach: For each find call, you would need to traverse the tree, reconstructing values on the fly. This would be O(N) per find call, where N is the number of nodes.
• Optimized approach (our solution):
  • Initialization: O(N) time and space to traverse and recover the tree, storing all values in a set.
  • Find operation: O(1) average time per call, since hash set lookups are constant time.
  • Space complexity: O(N) for storing all node values.

Summary

The main insight is to recover the contaminated tree only once, storing all valid node values in a hash set for efficient lookup. This design makes the find operation extremely fast, even if called many times. The solution leverages DFS for tree traversal and a set for O(1) lookups, making it both elegant and efficient for the problem's requirements.