1261. Find Elements in a Contaminated Binary Tree

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

Intuition

BFS/DFS the contaminated tree. Each node gets value 2*parent or 2*parent+1. Store all recovered values in a HashSet for O(1) find.

Algorithm

1DFS from root (value 0): left child = 2*val, right child = 2*val+1.
2Add all values to a HashSet.
3find(target): return target in set.

Common Pitfalls

•Root value is 0 in contaminated tree, not 0. Wait - original values are replaced with -1; use BFS to assign correct values.

1261.cs

// Approach: DFS to recover tree values (root=0, left=2*v+1, right=2*v+2) into a HashSet; Find() is O(1) lookup.
// Time: O(n) build, O(1) find Space: O(n)

public class TreeNode
{
    private HashSet<int> vals = new HashSet<int>();

    public FindElements(TreeNode root)
    {
        Dfs(root, 0);
    }

    public bool Find(int target)
    {
        return vals.Contains(target);
    }

    private void Dfs(TreeNode root, int val)
    {
        if (root == null)
            return;

        root.val = val;
        vals.Add(val);
        Dfs(root.left, val * 2 + 1);
        Dfs(root.right, val * 2 + 2);
    }
}

Was this solution helpful?