LeetCode 1261: Find Elements in a Contaminated Binary Tree Solution

Master LeetCode problem 1261 (Find Elements in a Contaminated Binary Tree), a medium challenge, with our optimized solutions in Java, C++, and Python. Explore detailed explanations, test your code in our interactive editor, and prepare for coding interviews.

1261. Find Elements in a Contaminated Binary Tree

Medium

Hash Table Tree Depth-First Search Breadth-First Search Design Binary Tree

Problem Explanation

Explanation:

We are given a contaminated binary tree where each node's value has been changed to -1.
The original binary tree followed a specific rule for values: root.val = 0, left child's value = 2 * parent's value + 1, right child's value = 2 * parent's value + 2.
We need to implement a class that can recover the original binary tree and check if a given value exists in the recovered tree.

Algorithm:

Initialize the root with value 0, and recursively recover the left and right subtrees.
Use a set to store all values in the recovered tree.
For the find function, simply check if the target value exists in the set.

Time Complexity:

Initialization: O(n) where n is the number of nodes
Finding: O(1)

Space Complexity:

Initialization: O(n) where n is the number of nodes
Finding: O(1)

Solution Code

import java.util.HashSet;
import java.util.Set;

class FindElements {
    private Set<Integer> values;

    public FindElements(TreeNode root) {
        values = new HashSet<>();
        recover(root, 0);
    }

    private void recover(TreeNode node, int val) {
        if (node == null) return;
        node.val = val;
        values.add(val);
        recover(node.left, 2 * val + 1);
        recover(node.right, 2 * val + 2);
    }

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

Try It Yourself

Loading code editor...

Frequently Asked Questions

How to solve LeetCode 1261 (Find Elements in a Contaminated Binary Tree)?

This page provides optimized solutions for LeetCode problem 1261 (Find Elements in a Contaminated Binary Tree) in Java, C++, and Python, along with a detailed explanation and an interactive code editor to test your code.

What is the time complexity of LeetCode 1261 (Find Elements in a Contaminated Binary Tree)?

The time complexity for LeetCode 1261 (Find Elements in a Contaminated Binary Tree) varies by solution. Check the detailed explanation section for specific complexities in Java, C++, and Python implementations.

Can I run code for LeetCode 1261 on DevExCode?

Yes, DevExCode provides an interactive code editor where you can write, test, and run your code for LeetCode 1261 in Java, C++, or Python.

Back to LeetCode Solutions