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

SimplyLeet
TagsDisclaimersPrivacyTermsContactAbout Us

Find Elements in a Contaminated Binary Tree

Difficulty: Medium

Problem Description

Given a binary tree with the following rules:

  1. root.val == 0
  2. 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.

Key Insights

  • The structure of the tree allows us to derive the values of nodes based on their parent's value.
  • We can perform a depth-first search (DFS) to recover the values of the tree.
  • A set can be used for fast lookups to verify if a value exists in the recovered tree.

Space and Time Complexity

Time Complexity: O(n) - where n is the number of nodes in the tree (for recovery). Space Complexity: O(n) - for storing the values in a set and the call stack in DFS.

Solution

To solve the problem, we will:

  1. Use a depth-first search (DFS) approach to traverse the contaminated binary tree and recover the values based on the given rules.
  2. Store the recovered values in a set for efficient lookup during the find operation.

Code Solutions

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

class FindElements:
    def __init__(self, root: TreeNode):
        self.values = set()  # Initialize a set to store the recovered values
        self.recover(root, 0)  # Start recovering the tree from root

    def recover(self, node: TreeNode, val: int):
        if node is None:
            return
        node.val = val  # Recover the value
        self.values.add(val)  # Add the value to the set
        self.recover(node.left, 2 * val + 1)  # Recover left child
        self.recover(node.right, 2 * val + 2)  # Recover right child

    def find(self, target: int) -> bool:
        return target in self.values  # Check if the target is in the set
← Back to All Questions