{x}
blog image

Find Elements in a Contaminated Binary Tree

Given a binary tree with the following rules:

  1. root.val == 0
  2. For any treeNode:
    1. If treeNode.val has a value x and treeNode.left != null, then treeNode.left.val == 2 * x + 1
    2. 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

Solution Explanation: 1261. Find Elements in a Contaminated Binary Tree

This problem involves recovering a contaminated binary tree and efficiently checking for the existence of a target value. The tree follows specific rules for node values: the root has value 0, and for any node with value x, its left child has value 2x + 1 and its right child has value 2x + 2. All node values are initially set to -1.

Approach: DFS and Hash Set

The most efficient approach combines Depth-First Search (DFS) with a hash set (or similar data structure like a set in Python or Java).

  1. Initialization (FindElements constructor):

    • We perform a DFS traversal of the binary tree, starting from the root.
    • During the traversal, we reconstruct the original values of the nodes using the given rules. The root is set to 0. If a node has value x, its left child is assigned 2x + 1, and its right child is assigned 2x + 2.
    • Simultaneously, we add each node's restored value to a hash set (self.s in Python, s in Java/C++/Go/TypeScript). This hash set acts as an index for efficient lookup.

  2. Search (find method):

    • To check if a target value exists, we simply look up the target in the hash set. This operation has a time complexity of O(1) on average due to the constant-time nature of hash table lookups.

Time and Space Complexity

  • Time Complexity:

    • Initialization: The DFS traversal takes O(N) time, where N is the number of nodes in the binary tree. Each node is visited once.
    • Search: Checking if a target exists in the hash set takes O(1) average time.
    • Overall: The overall time complexity is dominated by the initialization, resulting in O(N).

  • Space Complexity:

    • The hash set stores all the node values, which is at most N. Therefore, the space complexity is O(N).

Code Examples (Multiple Languages)

The provided code in Python, Java, C++, Go, and TypeScript all implement this approach. The core logic remains consistent: a DFS for reconstruction and a hash set for efficient searching. The specifics of hash set implementation vary slightly between languages. Each code snippet demonstrates this solution effectively.

Alternative Approaches

While this approach is optimal in terms of time complexity, alternative approaches exist (but are less efficient):

  • Level-order traversal (BFS): Similar to DFS, BFS can be used to recover the node values and store them in a hash set. This would still have O(N) time and space complexity.
  • Recursive search without hash set: A recursive search function could be implemented without a hash set to check for the target. However, this would have a much worse time complexity, potentially O(N) for each find operation in the worst case.

The DFS with a hash set method is superior because of its efficient O(1) average-case search time after the initial O(N) initialization.