Find Elements in a Contaminated Binary Tree - Medium Problem

This problem demonstrates clearly that both in Mathematics as well as in Computer Science/Algorithms, one of the key points to solving a problem correctly is understanding the problem correctly. Here we go https://leetcode.com/problems/find-elements-in-a-contaminated-binary-tree/

Given a binary tree with the following rules:

1. root.val == 0
2. If treeNode.val == x and treeNode.left != null, then treeNode.left.val == 2 * x + 1
3. If treeNode.val == 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.

You need to first recover the binary tree and then implement the FindElements class:

• FindElements(TreeNode* root) Initializes the object with a contamined binary tree, you need to recover it first.
• bool find(int target) Return 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 <= target <= 10^6

The main problem will be to Find the elements in the tree. Just a bool yay or nay. And if you notice, the max number of (integer) elements in the tree is 10,000. We're talking about storing 10,000 int. This is a tiny number which can be stored in a hash table. So from the get-go, the strategy will be to store the entire tree into a hash table to make the "Find" operation O(1)-time.

Next, we don't really need to set the value of each node in the tree. The problem is not asking for that. Hence, we can pretty much ignore the value of each node inside the Tree object, and only use the rules given to populate the hash table (we'll call it cache). That should do the trick. Cheers, ACC.

public class FindElements

{

    private Hashtable cache = new Hashtable();

    public FindElements(TreeNode root)

    {

        FillCache(root, 0);

    }

    public bool Find(int target)

    {

        return cache.ContainsKey(target);

    }

    private void FillCache(TreeNode node, int val)

    {

        if (node == null) return;

        if (!cache.ContainsKey(val)) cache.Add(val, true);

        FillCache(node.left, 2 * val + 1);

        FillCache(node.right, 2 * val + 2);

    }

}