Find Elements in a Contaminated Binary Tree

Medium

Asked by:

17 views

Topics:

TreesRecursion

Given a binary tree with the following rules:

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

Try coding it in LeetCode

Solution

Clarifying Questions

When you get asked this question in a real-life environment, it will often be ambiguous (especially at FAANG). Make sure to ask these questions in that case:

The problem statement mentions 'recovering' the tree. Does this mean I must modify the tree nodes in-place, or is it acceptable to build a separate data structure that stores the recovered values?
Given that the `find` method will be called multiple times after a single initialization, should I prioritize the performance of `find`, for instance aiming for O(1) time, even if it requires more pre-processing work in the constructor?
The recovery rules, `2*x + 1` for a left child and `2*x + 2` for a right child, seem to guarantee that all recovered node values will be unique. Is this a correct assumption?
The constraints state the number of nodes is at least one. Can I safely assume the root of the tree passed to the constructor will never be null?
The constraints mention the tree's height is at most 20, while the number of nodes is at most 10,000. This suggests the tree could be very sparse. Are there any memory usage constraints I should be aware of, especially if I consider storing all recovered values?

Brute Force Solution

Approach

The brute force strategy involves two main phases. First, we completely rebuild the tree by visiting every single node and calculating its correct value based on the given rules. Then, to find a specific number, we simply check every single one of the newly calculated values to see if we can find a match.

Here's how the algorithm would work step-by-step:

First, we need to figure out all the correct values that should be in the tree. Start by visiting the very top of the tree, the root, and assign it the value 0.
From the root, travel to its children and calculate their correct values using the special formula: a left child's value is twice its parent's value plus one, and a right child's value is twice its parent's value plus two.
Continue this process, moving down the tree from parent to child, until you have visited every single spot and calculated its correct value.
As you determine each correct value, add it to a collection that holds all the possible numbers in the recovered tree.
Now, when you're asked to find a specific target number, you simply take that number.
Go through your collection of correct values one by one.
Compare the target number to each value in your collection. If you find a match, then the number exists in the tree. If you check all the values and don't find a match, it doesn't.

Code Implementation

class FindElements:
    def __init__(self, root_node: TreeNode):
        self.recovered_root_node = root_node

        # We must first traverse the entire tree to replace the contaminated values with correct ones.
        
        self._recover(self.recovered_root_node, 0)

    def _recover(self, current_node, assigned_value):
        if current_node is None:
            return

        current_node.val = assigned_value

        # The recovery rule dictates a specific value calculation for left and right children.
        
        self._recover(current_node.left, 2 * assigned_value + 1)
        self._recover(current_node.right, 2 * assigned_value + 2)

    def find(self, target_value: int) -> bool:
        # Each find operation must re-scan the entire tree from the top to locate the target.
        
        return self._search(self.recovered_root_node, target_value)

    def _search(self, current_node, value_to_find):
        if current_node is None:
            return False

        # If the current node's value matches, we have successfully found the target in the tree.
        
        if current_node.val == value_to_find:
            return True

        # If not found, the search must continue down both the left and right paths from this node.
        
        return self._search(current_node.left, value_to_find) or self._search(current_node.right, value_to_find)

Big(O) Analysis

Time Complexity

O(n) – The time complexity is determined by two sequential phases, where 'n' is the number of nodes in the tree. The first phase involves a complete traversal of the tree to calculate and store the correct value for each of the 'n' nodes, which is an operation that scales linearly with n. The second phase, finding a target, requires a linear scan through the 'n' stored values. This search compares the target against each element one by one, also taking up to 'n' operations in the worst case. Therefore, the total operations are proportional to n + n, which simplifies to O(n).

Space Complexity

O(N) – The primary use of auxiliary space is the collection created to store all the recovered node values described in the steps. Since the algorithm visits every node and adds its unique calculated value, this collection will grow to hold exactly N items, where N is the total number of nodes in the tree. Additionally, the process of visiting every node requires a traversal, which uses space for a recursion stack or a queue that can be up to O(N) in the worst-case scenario. The space complexity is therefore dominated by storing N values, resulting in O(N).

Optimal Solution

Approach

The key idea is to first 'heal' the tree by calculating the correct value for every existing node in a one-time setup process. We then store all these correct values in a special collection that allows for super-fast lookups, which avoids having to search the entire tree every single time we need to find a number.

Here's how the algorithm would work step-by-step:

First, perform a one-time recovery of the entire tree to figure out the correct values.
Start at the top node, the root, and assign it the value of zero. Keep a master list of all the correct values you discover.
Add zero to your master list of discovered values.
Now, travel down the tree from parent to child. For each node you visit, calculate what its children's values should be.
The rule is simple: a left child's value is twice its parent's value plus one, and a right child's is twice its parent's value plus two.
As you travel to each existing child, calculate its correct value using this rule and add it to your master list.
After you have visited every node and recorded all their correct values, the recovery is done.
Now, whenever you are asked to find a target number, you don't need to search the tree. You just look for the number in your pre-built master list, which is a very fast check.

Code Implementation

class FindElements:
    def __init__(self, root):
        # Using a set is crucial for achieving the near-instant lookup time required.

        self.recovered_values_set = set()

        # We must traverse the entire tree once to calculate and store the correct value for each node.

        self._recover_tree_values(root, 0)

    def _recover_tree_values(self, current_node, calculated_value):
        if not current_node:
            return

        self.recovered_values_set.add(calculated_value)

        # The formula for children's values reconstructs the tree's intended structure.

        if current_node.left:
            self._recover_tree_values(current_node.left, (calculated_value * 2) + 1)
        
        if current_node.right:
            self._recover_tree_values(current_node.right, (calculated_value * 2) + 2)

    def find(self, target_value):
        # This check is fast because all values were pre-calculated and stored in a hash set.

        return target_value in self.recovered_values_set

Big(O) Analysis

Time Complexity

O(N) – The time complexity is determined by the initial one-time recovery process, where N is the total number of nodes in the tree. This recovery requires a complete traversal of the tree, such as a Depth-First Search, to visit every single node, calculate its correct value, and store it. Since each of the N nodes is processed exactly once during this setup phase, the total number of operations is directly proportional to N. Subsequent calls to find a target value are O(1) because they just involve a quick lookup in the pre-built set of values.

Space Complexity

O(N) – The primary space consumption comes from the 'master list' which is built to store the recovered value of every node in the tree. If the input tree contains N nodes, this master list will also store N distinct values, making its size directly proportional to N. Additionally, the one-time traversal of the tree requires auxiliary space for a recursion call stack or a queue. In the worst case, this traversal space can also be O(N), leading to a total auxiliary space complexity of O(N).

Edge Cases

Case	How to Handle
Constructor is initialized with a null root.	The implementation should handle this by treating the tree as empty, causing all subsequent find calls to return false.
The tree consists of only a single root node.	The recovery process correctly identifies the root's value as 0, so find(0) returns true while any other target returns false.
A degenerate tree that resembles a linked list, for example, all nodes are only left children.	The chosen data structure, like a hash set, is unaffected by the tree's shape, ensuring consistent performance.
Finding a target value that is missing in the given sparse tree but would exist in a complete tree.	The recovery process only stores values for existing nodes, so searching for a value corresponding to a null child path correctly returns false.
The find method is called with a target of 0.	This corresponds to the root of the tree, which is guaranteed to exist by the constraints, so the solution should always return true.
The tree has the maximum allowed height of 20, leading to potentially large node values.	The largest possible node value, approximately 2^20, fits within a standard 32-bit integer, preventing overflow during value calculation.
The system is tested against the maximum constraints: 10^4 nodes and 10^4 find calls.	A pre-computation approach using a hash set provides O(1) average time for each find call, which is necessary to pass within time limits.
The find method is called multiple times with different targets on the same initialized object.	The recovered values are stored in a persistent data structure during initialization, allowing repeated queries to be answered efficiently without re-traversing the tree.

Constructor is initialized with a null root.

How to Handle:

The implementation should handle this by treating the tree as empty, causing all subsequent find calls to return false.

The tree consists of only a single root node.

How to Handle:

The recovery process correctly identifies the root's value as 0, so find(0) returns true while any other target returns false.

A degenerate tree that resembles a linked list, for example, all nodes are only left children.

How to Handle:

The chosen data structure, like a hash set, is unaffected by the tree's shape, ensuring consistent performance.

Finding a target value that is missing in the given sparse tree but would exist in a complete tree.

How to Handle:

The recovery process only stores values for existing nodes, so searching for a value corresponding to a null child path correctly returns false.

The find method is called with a target of 0.

How to Handle:

This corresponds to the root of the tree, which is guaranteed to exist by the constraints, so the solution should always return true.

The tree has the maximum allowed height of 20, leading to potentially large node values.

How to Handle:

The largest possible node value, approximately 2^20, fits within a standard 32-bit integer, preventing overflow during value calculation.

The system is tested against the maximum constraints: 10^4 nodes and 10^4 find calls.

How to Handle:

A pre-computation approach using a hash set provides O(1) average time for each find call, which is necessary to pass within time limits.

The find method is called multiple times with different targets on the same initialized object.

How to Handle:

The recovered values are stored in a persistent data structure during initialization, allowing repeated queries to be answered efficiently without re-traversing the tree.