1261. Find Elements in a Contaminated Binary Tree LeetCode Solution

In this guide, you will get 1261. Find Elements in a Contaminated Binary Tree LeetCode Solution with the best time and space complexity. The solution to Find Elements in a Contaminated Binary Tree problem is provided in various programming languages like C++, Java, and Python. This will be helpful for you if you are preparing for placements, hackathons, interviews, or practice purposes. The solutions provided here are very easy to follow and include detailed explanations.

Problem Statement
Complexity Analysis
Find Elements in a Contaminated Binary Tree solution in C++
Find Elements in a Contaminated Binary Tree solution in Java
Find Elements in a Contaminated Binary Tree solution in Python
Additional Resources

1261. Find Elements in a Contaminated Binary Tree LeetCode Solution image

Problem Statement of Find Elements in a Contaminated Binary Tree

Given a binary tree with the following rules:

root.val == 0
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, 104]
Total calls of find() is between [1, 104]
0 <= target <= 106

Complexity Analysis

Time Complexity:
Space Complexity:

1261. Find Elements in a Contaminated Binary Tree LeetCode Solution in C++

class FindElements {
 public:
  FindElements(TreeNode* root) {
    dfs(root, 0);
  }

  bool find(int target) {
    return vals.contains(target);
  }

 private:
  unordered_set<int> vals;

  void dfs(TreeNode* root, int val) {
    if (root == nullptr)
      return;

    root->val = val;
    vals.insert(val);
    dfs(root->left, val * 2 + 1);
    dfs(root->right, val * 2 + 2);
  }
};
/* code provided by PROGIEZ */

1261. Find Elements in a Contaminated Binary Tree LeetCode Solution in Java

class FindElements {
  public FindElements(TreeNode root) {
    dfs(root, 0);
  }

  public boolean find(int target) {
    return vals.contains(target);
  }

  private Set<Integer> vals = new HashSet<>();

  private void dfs(TreeNode root, int val) {
    if (root == null)
      return;

    root.val = val;
    vals.add(val);
    dfs(root.left, val * 2 + 1);
    dfs(root.right, val * 2 + 2);
  }
}
// code provided by PROGIEZ

1261. Find Elements in a Contaminated Binary Tree LeetCode Solution in Python

class FindElements:
  def __init__(self, root: TreeNode | None):
    self.vals = set()
    self.dfs(root, 0)

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

  def dfs(self, root: TreeNode | None, val: int) -> None:
    if not root:
      return

    root.val = val
    self.vals.add(val)
    self.dfs(root.left, val * 2 + 1)
    self.dfs(root.right, val * 2 + 2)
 # code by PROGIEZ