We use cookies (including Google cookies) to personalize ads and analyze traffic. By continuing to use our site, you accept our Privacy Policy.

SimplyLeet
TagsCompaniesDisclaimersPrivacyTermsContactAbout Us

Find Elements in a Contaminated Binary Tree

Number: 1387

Difficulty: Medium

Paid? No

Companies: Amazon, Google

Problem Description

You are given a contaminated binary tree where every node’s value is -1. The original tree was constructed with the rule that the root is 0, and for any node with value x, its left child is 2 * x + 1 and its right child is 2 * x + 2 (if they exist). Your task is to recover the tree and implement a method called find(int target) to check if a given target value exists in the recovered tree.

Key Insights

  • Recover the binary tree using either depth-first search (DFS) or breadth-first search (BFS).
  • Each node’s original value can be computed based on its parent's value using the formulas: left child = 2 * parent's value + 1, right child = 2 * parent's value + 2.
  • Store the recovered node values in a HashSet for O(1) lookup during find queries.
  • Preprocessing the tree (recovering and populating the set) takes O(n) time, while each find operation is O(1).

Space and Time Complexity

Time Complexity:

  • Initialization (recovering the tree): O(n) where n is the total number of nodes.
  • Find queries: O(1) per query.

Space Complexity:

  • O(n) for storing node values in a set, plus O(n) for the recursion/queue in DFS/BFS, which simplifies to O(n).

Solution

The solution consists of two primary steps:

  1. Recover the contaminated binary tree: Starting from the root (set to 0), traverse the tree using DFS or BFS. For each node, compute and assign its correct value based on the given formulas. As you traverse, record each computed node value in a HashSet.
  2. Implement the find(target) method: Simply check whether the target exists in the HashSet. This provides a fast O(1) lookup.

The key trick is to preprocess the tree once and reuse the stored values for efficient lookups. This method avoids repeated recomputation and makes the implementation simple and efficient.

Code Solutions

# Define the TreeNode structure
class TreeNode:
    def __init__(self, val=0, left=None, right=None):
        self.val = val
        self.left = left
        self.right = right

class FindElements:
    # Initialize and recover the tree
    def __init__(self, root: TreeNode):
        # HashSet to store recovered values for constant time lookups.
        self.values = set()
        # Begin recovery from the root, with its corrected value of 0.
        self.recover(root, 0)
    
    def recover(self, node: TreeNode, value: int):
        # If the node does not exist, exit recursion.
        if not node:
            return
        # Assign the recovered value to the current node.
        node.val = value
        # Add the value to the set.
        self.values.add(value)
        # If left child exists, recover its value: 2 * current value + 1.
        self.recover(node.left, 2 * value + 1)
        # If right child exists, recover its value: 2 * current value + 2.
        self.recover(node.right, 2 * value + 2)
    
    # Method to find if target value exists in the tree.
    def find(self, target: int) -> bool:
        return target in self.values

# Example usage:
# Construct a contaminated binary tree manually
# For example, a tree like [-1, None, -1]
if __name__ == "__main__":
    root = TreeNode(-1)
    root.right = TreeNode(-1)
    findElements = FindElements(root)
    print(findElements.find(1))  # Expected output: False
    print(findElements.find(2))  # Expected output: True
← Back to All Questions