🔥🔥||Easy Solution||Beats 100% in most||With proof||💎☕🖥️🐍C#️⃣C➕➕✅||🔥🔥
Intuition💡It's obvious to use BFS for the initial part. However, a lot of people use HashSet(set() in python) to pre-store all the values in the initial part, w
# Intuition💡
It's obvious to use `BFS` for the initial part. However, a lot of people use HashSet(`set()` in python) to pre-store all the values in the initial part, which may cause MLE when the values are huge. There is a special way to implement `find()` that costs O(1) in space and O(logn) in time.

# Approach🚀
- Declare a HashSet `seen` as a member of the `FindElements` class
- For helper function `dfs(currentNode, currentValue, seen)`:
- For `find(target)` function:
# Complexity⌚
- Time complexity: O(n)

- Space complexity: O(MAX)
Constraints say that 0 <= target <= 10^6, so we store bitset<10^6 + 1>

# Code
```cpp []
class FindElements {
public:
    FindElements(TreeNode* root) { dfs(root, 0); }

    bool find(int target) { return seen.count(target) > 0; }

private:
    unordered_set<int> seen;

    void dfs(TreeNode* currentNode, int currentValue) {
        if (!currentNode) return;
        // visit current node by adding its value to seen
        seen.insert(currentValue);
        dfs(currentNode->left, currentValue * 2 + 1);
        dfs(currentNode->right, currentValue * 2 + 2);
    }
};
```
```Rust []
// #[derive(Debug, PartialEq, Eq)]
// pub struct TreeNode {
//   pub val: i32,
//   pub left: Option<Rc<RefCell<TreeNode>>>,
//   pub right: Option<Rc<RefCell<TreeNode>>>,
// }
use std::{cell::RefCell, rc::Rc};

struct FindElements {
    root: Option<Rc<RefCell<TreeNode>>>,
}

impl FindElements {
    fn new(root: Option<Rc<RefCell<TreeNode>>>) -> Self {
        // Encapsulate in a dummy root for checks.
        let root = Some(Rc::new(RefCell::new(TreeNode {
            val: -1,
            left: None,
            right: root,
        })));
        Self { root }
    }
    
    fn find(&self, target: i32) -> bool {
        if target < 0 {
            return false;
        }
        // Not necessary for problem constraints, but needed to handle
        // trees with deeper levels.
        let adjusted = target as u32 + 1;
        let mut offset_opt = Some(adjusted.ilog2());
        let mut node = self
            .root
            .clone()
            .expect("The structure should always have a dummy root");
        while let Some(offset) = offset_opt {
            // Get the proper node depending upon the check bit.
            let opt = if ((adjusted >> offset) & 1) == 1 {
                node.borrow().right.clone()
            } else {
                node.borrow().left.clone()
            };
            // Fail early if the node is not found.
            node = match opt {
                None => return false,
                Some(node) => node,
            };
            offset_opt = offset.checked_sub(1);
        }
        true
    }
}
```
```C# []
/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     public int val;
 *     public TreeNode left;
 *     public TreeNode right;
 *     public TreeNode(int val=0, TreeNode left=null, TreeNode right=null) {
 *         this.val = val;
 *         this.left = left;
 *         this.right = right;
 *     }
 * }
 */
public class FindElements {

    TreeNode root = null;
public FindElements(TreeNode root)
{
    this.root = root;
    RecoverElements(this.root, 0);
}

public bool Find(int target)
{
    var s = this.GetPath4Target(target);
    TreeNode cur = this.root;
    while (s.Count > 0)
{
    int v = s.Pop();
    if (cur == null || cur.val != v)
    {
        return false;
    }
    if (s.Count > 0 && cur.left != null && cur.left.val == s.Peek())
    {
        cur = cur.left;
    }
    else
    {
        cur = cur.right;
    }
}
    return true;
}
private void RecoverElements(TreeNode root, int rootValue)
{
    root.val = rootValue;
    if (root.left != null)
    {
        RecoverElements(root.left, rootValue * 2 + 1);
    }
    if (root.right!=null)
    {
        RecoverElements(root.right, rootValue * 2 + 2);
    }
}
private Stack<int> GetPath4Target(int target)
{
    Stack<int> result = new Stack<int>();
    while (target > 0)
    {
        result.Push(target);
        int reminder = target % 2 != 0 ? 1 : 2;
        target = (target - reminder) >> 1;
    }
    result.Push(0);
    return result;
}
}

/**
 * Your FindElements object will be instantiated and called as such:
 * FindElements obj = new FindElements(root);
 * bool param_1 = obj.Find(target);
 */
```
```C []
class FindElements {
    TreeNode* head=new TreeNode(-1);
public:
    FindElements(TreeNode* root) {
        head=root;
        head->val=0;
        recover(head);
    }
    
    void recover(TreeNode* root)
    {
        if(root->left)
        {
            root->left->val=(root->val)*2+1;
            recover(root->left);
        }
        if(root->right)
        {
            root->right->val=(root->val)*2+2;
            recover(root->right);
        }
        return;
    }
    
    bool find(int target) {
        return get(target,head);
    }
    
    bool get(int target,TreeNode* root)
    {
        if(root==NULL)
            return false;
        if(root->val==target)
            return true;
        
        bool t1=get(target,root->left);
        bool t2=get(target,root->right);
        
        if(t1||t2)
            return true;
        return false;
    }
};
```
```Go []
/**
 * Definition for a binary tree node.
 * type TreeNode struct {
 *     Val int
 *     Left *TreeNode
 *     Right *TreeNode
 * }
 */
type FindElements struct {
    set map[int]bool
}

func (this *FindElements)constructTree(root *TreeNode, x int) {
    if root==nil {
        return
    }
    root.Val=x
    this.set[x]=true 
    this.constructTree(root.Left, (2*x)+1)
    this.constructTree(root.Right, (2*x)+2)
}
func Constructor(root *TreeNode) FindElements {
    m:=map[int]bool{}
    
    this:=FindElements{}
    this.set=m
    this.constructTree(root, 0)
    return this
}


func (this *FindElements) Find(target int) bool {
    return this.set[target];
}


/**
 * Your FindElements object will be instantiated and called as such:
 * obj := Constructor(root);
 * param_1 := obj.Find(target);
 */
```
```Ruby []
# Definition for a binary tree node.
# class TreeNode
#     attr_accessor :val, :left, :right
#     def initialize(val = 0, left = nil, right = nil)
#         @val = val
#         @left = left
#         @right = right
#     end
# end
class FindElements

=begin
    :type root: TreeNode
=end
    def initialize(root)
        @vals = Hash.new(false)
        if root
            @vals[0] = true
        end
        root.val = 0
        recover root
    end

    def recover node
        x = node.val
        if node.left
            val = 2 * x + 1
            @vals[val] = true
            node.left.val = val
            recover node.left
        end

        if node.right
            val = 2 * x + 2
            @vals[val] = true
            node.right.val = 2 * x + 2
            recover node.right
        end
    end


=begin
    :type target: Integer
    :rtype: Boolean
=end
    def find(target)
        @vals[target]
    end


end

# Your FindElements object will be instantiated and called as such:
# obj = FindElements.new(root)
# param_1 = obj.find(target)
```
```Java []
class FindElements {
    TreeNode root;
    Set<Integer> set = new HashSet<>();
    public FindElements(TreeNode root) {
        this.root = root;
        if(root != null){ root.val = 0; set.add(root.val); }
        recover(root,set);
    }
    
    public boolean find(int target) {
      return set.contains(target);
    }

    private void recover(TreeNode root, Set<Integer> set){
        if(root.left != null){
            root.left.val = 2 * root.val + 1;
            set.add(root.left.val);
            recover(root.left, set);
        }
       if(root.right != null){
            root.right.val = 2 * root.val + 2;
            set.add(root.right.val);
            recover(root.right, set);
       } 
    }
}
```
```javascript []
/**
 * Definition for a binary tree node.
 * function TreeNode(val, left, right) {
 *     this.val = (val===undefined ? 0 : val)
 *     this.left = (left===undefined ? null : left)
 *     this.right = (right===undefined ? null : right)
 * }
 */

function ListNode(val, next) {
    this.val = (val === undefined ? 0 : val)
    this.next = (next === undefined ? null : next)
}
/**
 * @param {TreeNode} root
 */
var FindElements = function (root) {
    this.elements = root
};

/** 
 * @param {number} target
 * @return {boolean}
 */
FindElements.prototype.find = function (target) {
    const head = createLinkedList(target)

    return dfs(this.elements, head)
};

const createLinkedList = (target) => {
    let prev = null

    while (target >= 0) {
        let current = new ListNode(target, prev)
        prev = current;

        target = target % 2 === 0 ? (target - 2) / 2 : (target - 1) / 2
    }

    return prev.next;
}

const dfs = (root, head) => {
    if (!root) return false;
    if (!head) return true;

    return head.val % 2 === 0 ? dfs(root.right, head.next) : dfs(root.left, head.next)
}

/** 
 * Your FindElements object will be instantiated and called as such:
 * var obj = new FindElements(root)
 * var param_1 = obj.find(target)
 */
```
![plez upvote.png](https://assets.leetcode.com/users/images/34097f82-737f-4eae-b5c5-2b75c9608e06_1739681400.6369047.png)

['C++']