Find Elements in a Contaminated Binary Tree

Leetcode Problem:

• Find Elements in a Contaminated Binary Tree

Summary

• The problem requires to recover a binary tree from a contaminated tree where all node values are -1 and then find if a target value exists in the recovered tree.

Approach

• The solution uses a helper function traversal to populate a boolean array s with the original values of the binary tree
• The traversal function is a depth-first search that assigns the original values to the nodes and marks them in the s array
• The find function simply checks the s array for the target value.

Complexity

• O(n), where n is the number of nodes in the tree, because each node is visited once during the traversal.

Explanation

• The solution uses a boolean array s of size 2000001 to keep track of the original values of the nodes
• The traversal function is a recursive depth-first search that assigns the original values to the nodes and marks them in the s array
• The find function simply checks the s array for the target value
• This approach ensures that the original values are recovered and can be used to check for the existence of a target value.

Solution Code:

/**
 * 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:
    bool s[2000001] = {0};
    void traversal(TreeNode* root, int val){
        if(root == nullptr) return;
        root->val = val;
        s[val] = true;
        traversal(root->left, val*2 + 1);
        traversal(root->right, val*2 + 2);
    }
    FindElements(TreeNode* root) {
        traversal(root, 0);
    }
    
    bool find(int target) {
        return s[target];
    }
};

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