Problem Informations

• Problem Index: 1261
• Problem Link: Find Elements in a Contaminated Binary Tree
• Topics: Hash Table, Tree, Depth-First Search, Breadth-First Search, Design, Binary Tree

Problem Description

Given a binary tree with the following rules:

1. root.val == 0
2. For any treeNode:
   • If treeNode.val has a value $x$ and treeNode.left != null, then treeNode.left.val == 2 * x + 1
   • If treeNode.val has a value $x$ and treeNode.right != null, then treeNode.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) Returns true if the target value 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, 10^4]$
• Total calls of find() is between $[1, 10^4]$
• $0 \leq target < 10^6$

Intuition

The problem involves recovering a binary tree that has been contaminated, with all node values set to -1. The tree follows a specific structure based on certain rules. To efficiently find if a target value exists in this recovered tree, we need a strategy that leverages the properties of the binary tree. The key observation here is that if we can recover the tree in some form, checking for the existence of a target is simply about verifying if it belongs to this structure.

Approach

The approach to solving this problem includes the following steps:

1. Tree Recovery: Initially, we need to reconstruct the tree based on the rules given:

   • Start with the root node, which by definition should have a value of 0.
   • For each node at a position $x$, its left child will have a value of $2x + 1$, and its right child will have a value of $2x + 2$.

   We use a recursive method recoverTree to achieve this. Starting from the root with an index of 0, we recursively set the values of the children nodes based on the above formulas. During this process, we also store the recovered values in a set to allow efficient lookup operations.

2. Efficient Lookup: To efficiently check if a target value exists in the recovered tree, we maintain a set of all recovered values. The find method is essentially a check to see if the target exists within this set. This provides an average time complexity of $O(1)$ for lookups due to the properties of hash-based sets.

3. Implementation Details:

   • The recoverTree function is responsible for assigning the correct values to each node according to the tree structure rules.
   • The FindElements constructor initializes this recovery process, ensuring that as soon as an object is created, the binary tree is reconstructed.
   • The find function then uses the pre-populated set of recovered values to determine if the given target exists in the tree.

By leveraging the properties of the specific rule-based tree structure and efficiently storing the recovered values, we achieve both reconstruction and search in an optimal manner.

Code

C++

/**
 * 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 {
public:
    // A set to store the recovered node values.
    set<int> recoveredValues;

    // Helper function to recover the binary tree.
    void recoverTree(TreeNode* root, int index) {
        if (root == nullptr) return;
        
        // Insert the computed index value for the current node.
        recoveredValues.insert(index);

        // Recursively recover the left child.
        recoverTree(root->left, index * 2 + 1);

        // Recursively recover the right child.
        recoverTree(root->right, index * 2 + 2);
    }

    // Constructor that initiates the recovery of the binary tree.
    FindElements(TreeNode* root) {
        // Start the recovery process from index 0 (root).
        recoverTree(root, 0);
    }
    
    // Method to find if the target exists in the recovered tree.
    bool find(int target) {
        // Check if the target is in the set of recovered values.
        return recoveredValues.count(target);
    }
};

/**
 * Your FindElements object will be instantiated and called as such:
 * FindElements* obj = new FindElements(root);
 * bool param_1 = obj->find(target);
 */

Python

# 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:
    # A set to store the recovered node values.
    def __init__(self, root: TreeNode):
        self.recoveredValues = set()
        
        # Start the recovery process from index 0 (root).
        self.recoverTree(root, 0)
    
    # Helper function to recover the binary tree.
    def recoverTree(self, root: TreeNode, index: int):
        if root is None:
            return
        
        # Insert the computed index value for the current node.
        self.recoveredValues.add(index)
        
        # Recursively recover the left child.
        self.recoverTree(root.left, index * 2 + 1)
        
        # Recursively recover the right child.
        self.recoverTree(root.right, index * 2 + 2)
    
    # Method to find if the target exists in the recovered tree.
    def find(self, target: int) -> bool:
        # Check if the target is in the set of recovered values.
        return target in self.recoveredValues

# Your FindElements object will be instantiated and called as such:
# obj = FindElements(root)
# param_1 = obj.find(target)

Complexity

• Time complexity:

  The FindElements class primarily involves two operations: tree recovery and target searching.

  1. Tree Recovery:

     • The recoverTree function is a recursive function that visits each node of the tree exactly once.
     • Given that the number of nodes, $n$, can be at most $10^4$, the time complexity for recovering the tree is $O(n)$.

  2. Target Searching:

     • The find method checks for the existence of target in a set, which is implemented as a balanced binary search tree (e.g., Red-Black Tree).
     • The count operation in a set has a time complexity of $O(\log n)$.
     • With the constraint of having at most $10^4$ calls to find, each call independently runs in $O(\log n)$ time.

  Combining both operations, the overall time complexity combines the recovery phase and each call to find, giving us $O(n + m \log n)$, where $m$ is the number of find calls, which is bounded by $10^4$.

• Space complexity:

  1. Tree Recovery Storage:

     • The primary additional space usage is for the recoveredValues set, which stores all node values for recovered binary tree nodes.
     • In the worst-case scenario, there are $n$ nodes, and hence $O(n)$ space is used.

  2. Recursive Stack:

     • The recursive recoverTree function will use space proportional to the height of the tree.
     • Given that the height of the binary tree is bounded by $20$, the recursive call stack space used is $O(20) \equiv O(1)$.

  Thus, the overall space complexity is $O(n)$ due to the set storage.