Beat 100% | Most optimal | Bit manipulation + binary search in Python and C# | O(log(n)) time
IntuitionThe key observation is that we do not actually need to “recover” the whole tree explicitly. Given the recovery rules—assigning the root a value of 0 an
# Intuition
The key observation is that we do not actually need to “recover” the whole tree explicitly. Given the recovery rules—assigning the root a value of 0 and for any node with value x, its left child is 2\*x + 1 and its right child is 2\*x + 2—we can deduce that if we add 1 to any target value, its binary representation (ignoring the most significant bit) naturally encodes the path from the root:
- A 0 bit indicates a move to the left child.
- A 1 bit indicates a move to the right child.

Thus, we can simulate following this path in the tree starting from the root without having to recover every node’s value.

# Approach
1. Handle the Root Case:
If the target value is 0, simply check if the root exists.
2. Determine the Path:
- Compute `path = target + 1`.
- The binary representation of `path` (minus its leading bit) tells us how to navigate the tree.
- Use $$\log _{2}(path)$$ to determine the depth (or number of decision steps) needed to reach the target.
3. Traverse the Tree:
- Initialize a pointer at the root.
- Create a mask starting at `1 << (depth - 1)` to examine each bit from most significant to least significant.
- For each bit:
    - If the bit is 0, move to the left child.
    - If the bit is 1, move to the right child.
    - If at any point the pointer becomes null, the target value does not exist in the tree.
4. Return the Result:
- After following the entire bit path, if the pointer is not null, then the target exists in the tree.

# Complexity
- Time complexity: $$O(log(target))$$ for `find(target)`, $$O(1)$$ for `FindElements(root)`
The algorithm examines each bit in the binary representation of `target + 1`, which takes $$O(d)$$ time where d is the depth of the node. For a complete binary tree, this is $$O(log n)$$.

- Space complexity: $$O(1)$$
Only a constant amount of extra space is used, $$O(1)$$.

# Code
```python []
class FindElements:
    def __init__(self, root: Optional[TreeNode]):
        self.root = root

    def find(self, target: int) -> bool:
        if target == 0:
            return self.root is not None
        
        path = target + 1
        depth = path.bit_length() - 1
        node = self.root
        mask = 1 << (depth - 1)
        while mask > 0 and node is not None:
            node = node.left if (path & mask) == 0 else node.right    
            mask >>= 1
        
        return node is not None
```
```csharp []
public class FindElements {
    private readonly TreeNode _root;

    public FindElements(TreeNode root)
    {
        _root = root;
    }

    public bool Find(int target)
    {
        if (target == 0)
        {
            return _root != null;
        }
        
        var path = target + 1;
        var depth = int.Log2(path);
        var node = _root;
        var mask = 1 << (depth - 1);
        while (mask > 0 && node != null)
        {
            node = (path & mask) == 0 ? node.left : node.right;
            mask >>= 1;
        }

        return node != null;
    }
}
```

# Code (Trditional Binary Search)
```csharp []
public class FindElements
{
    private readonly TreeNode? _root;

    public FindElements(TreeNode root)
    {
        _root = root;
    }

    public bool Find(int target)
    {
        if (target == 0)
        {
            return _root != null;
        }

        target++;
        var depth = int.Log2(target);
        var node = _root;
        
        var low = 1 << depth;
        var high = (1 << (depth + 1)) - 1;

        while (depth > 0 && node != null)
        {
            var mid = low + ((high - low) >> 1);
            if (mid >= target)
            {
                if (node.left == null)
                {
                    return false;
                }

                high = mid;
                node = node.left;
            }
            else
            {
                if (node.right == null)
                {
                    return false;
                }

                low = mid + 1;
                node = node.right;
            }

            depth--;
        }

        return true;
    }
}
``` 

['Binary Search', 'Bit Manipulation', 'Binary Search Tree', 'Binary Tree', 'Bitmask', 'Python3', 'C#']