Find Elements in a Contaminated Binary Tree

Problem

Given a binary tree with the following rules:

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

Examples

Example 1:

graph LR

subgraph Original
	A1(("-1"))
	B1:::hidden
	C1(("-1"))
	A1 ~~~ B1
	A1 --> C1

end

subgraph After["Recovered"]
	A2((0))
	B2:::hidden
	C2((2))

	A2 ~~~ B2
	A2 --> C2
end

Original --> After

classDef hidden display: none;

**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:

graph LR

    subgraph Original
        A1(("-1"))
        B1(("-1"))
        C1(("-1"))
        D1(("-1"))
        E1(("-1"))
        
        A1 --> B1 & C1
        B1 --> D1 & E1
    end
    
    subgraph After["Recovered"]
        A2((0))
        B2((1))
        C2((2))
        D2((3))
        E2((4))

        A2 --> B2 & C2
        B2 --> D2 & E2
    end
    
    Original --> After
    

**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:

graph LR

subgraph Original
	A1(("-1"))
	B1:::hidden
	C1(("-1"))
	D1(("-1"))
	E1
	F1(("-1"))
	G1

	A1 ~~~ B1
	A1 --> C1
	C1 --> D1
	C1 ~~~ E1:::hidden
	D1 --> F1
	D1 ~~~ G1:::hidden
end

subgraph After["Recovered"]
	A2((0))
	B2:::hidden
	C2((2))
	D2(("5"))
	E2
	F2(("11"))
	G2	

	A2 ~~~ B2
	A2 --> C2
	C2 --> D2
	C2 ~~~ E2:::hidden
	D2 --> F2
	D2 ~~~ G2:::hidden	
end

Original --> After

classDef hidden display: none;

**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^4]
• Total calls of find() is between [1, 10^4]
• 0 <= target <= 10^6

Solution

The problem requires us to reconstruct the original values of a contaminated binary tree, where every node initially had a specific value following certain rules. All node values of the tree are replaced by -1, and we need to:

1. Recover the Tree Values: Based on the rules of node recovery:
   • If a node x has a left child, the left child value is given by 2 * x + 1.
   • If a node x has a right child, the right child value is 2 * x + 2.
   • The root has a value 0.
2. Find Target in the Recovered Tree: To check if a target value exists in the recovered tree.

Method 1 - DFS

Here is how we will solve it:

• Recover the Tree:
  • Use a recursive DFS starting from the root. Set the root's value to 0 and propagate the rules for its left and right nodes.
• Find Method:
  • Use a HashSet (or equivalent) to store all the recovered node values for O(1) retrieval.

Video explanation

Here is the video explaining this method in detail. Please check it out:

<div class="youtube-embed"><iframe src="https://www.youtube.com/embed/tE7PHiP5Unw" frameborder="0" allowfullscreen></iframe></div>

Code

Java

class FindElements {
    private Set<Integer> nodes;

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

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

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

Python

class FindElements:
    def __init__(self, root: Optional[TreeNode]):
        self.nodes: Set[int] = set()
        self.recover(root, 0)
    
    def recover(self, node: Optional[TreeNode], v: int) -> None:
        if not node:
            return
        node.val = v
        self.nodes.add(v)
        self.recover(node.left, 2 * v + 1)
        self.recover(node.right, 2 * v + 2)
    
    def find(self, target: int) -> bool:
        return target in self.nodes

Complexity

• ⏰ Time complexity:
  • Recover: O(n) (where n is the number of nodes).
  • Find: O(1) as it uses hashset
• 🧺 Space complexity: O(n) due to the hash set storing node values + recursion stack in DFS