NEW Approach! Branchless. Time O(1) OR space O(1). Beats 100.00%
IntuitionDepth-first tree traversal, calculating the values ​​of child nodes using formula2 * x + 1and2 * x + 2forleftandright. Use aSetorArrayto store node val
# Intuition
Depth-first tree traversal, calculating the values ​​of child nodes using formula `2 * x + 1` and `2 * x + 2` for `left` and `right`. Use a `Set` or `Array` to store node values.

To fit into `O(1)` space, you can honestly search for a path along the tree. To do this, use the formulas above and restore the entire path in reverse order. If `target` is even, then the last turn was to the `right`, otherwise to the `left`.

# UPD! New Approach: Faster way
1. In constructor, just save the link to the root.
2. Instead of using the formulas above, you can use the bits of the `target`. You need to add `1` and ignoring the MSB (the leftmost `1` bit), starting with the bit after it, move so that bit `0` is a `left` turn, bit `1` is a `right` turn. You can find the most significant bit using `32 - countl_zero(x)` in C++ or `32 - Math.clz32(x)` in JS .

It is fast(`0ms C++`, `4ms JS`), `O(1)` space and not modifying the original tree.

![2.png](https://assets.leetcode.com/users/images/6c960784-1812-4587-89b1-ffba0f1636a6_1740244064.2550344.png)



# Approach DFS
1. DFS in constructor. Save `val` in Set/Array.
2. Check `target` in Set/Array.

![1.png](https://assets.leetcode.com/users/images/16d662b7-c2f5-4a05-bb05-0588f768eeb6_1740139148.5900943.png)


# Approach Find path
1. In constructor, just save the link to the root.
2. Find da wae: If `t` is even, then `2` was added to it, that is, the last turn was to the right. If it is odd, then `1` was added and the last turn was to the left. Subtract `1` or `2` from `t`, depending on the parity, and divide by `2`. Continue until find the entire path from the last to the first turn.
3. Follow da wae: Follow the found path, remembering that it is reversed. If the last node is not null, then `t` is found.

To make it more fun, I decided to make a branchless loop using a table for follow the found path, and got an expression like `x[y[z.pop()]]`. If we choose appropriate variable names, we get:`show[me[da[wae]()]]`.

# Complexity
- Time complexity `constructor`: Fast way/Da Wae $$O(1)$$, Set/Array $$O(n)$$
<!-- Add your time complexity here, e.g. $$O(n)$$ -->
- Time complexity `find`: Set/Array $$O(1)$$, Fast way/Da Wae $$O(log(t))$$.
<!-- Add your time complexity here, e.g. $$O(n)$$ -->
- Space complexity: Fast way $$O(1)$$, Da Wae $$O(log(n))$$, Set/Array $$O(n)$$
<!-- Add your space complexity here, e.g. $$O(n)$$ -->

# Code C++
```javascript [New Fast way]
class FindElements {
public:
    TreeNode *r;
    FindElements(TreeNode *root) { // O(1)
        r = root;
    }
    
    bool find(int t) {  // branchless O(log(t))
        if (t == 0) return true;
        TreeNode *n = r;
        TreeNode *TreeNode:: *side[] = {&TreeNode::left, &TreeNode::right};
        for (int i = 30 - countl_zero((uint)++t); n && i >= 0; --i)
            n = n->*(side[(t & (1 << i)) > 0]); // 0 - left, 1 - right
        return n;
    }
};
```
# Code JS
```javascript [New Fast way]
class FindElements {
    constructor(r) { // O(1)
        this.r = r;
    }

    find(t) { // branchless O(log(t))
        if (t === 0) return true;
        let n = this.r;
        const side = ['left', 'right'];
        for (let i = 30 - Math.clz32(++t); n && i >= 0; --i)
            n = n[side[(t & (1 << i)) >> i]]; // 0 - left, 1 - right
        return !!n;
    }
};
```
```javascript [Da Wae]
class FindElements {
    constructor(r) { // O(1)
        this.r = r;
    }

    find(t) { // branchless O(log(t))
        if (t === 0) return true;
        const da = [];
        while (t > 0) {
            da.push(t & 1); // 1 - left, 0 - right
            t = (t - (1 << (!(t & 1)))) >> 1;
        }
        const me = ['right', 'left'];
        const wae = 'pop';
        let show = this.r;
        while (show && da.length)
            show = show[me[da[wae]()]];
        return !!show;
    }
};
```
```javascript [Stack/Set]
class FindElements {
    s = new Set();

    constructor(r) { // O(n)
        const a = [r];
        r.val = 0;
        while (a.length) {
            const n = a.pop();
            this.s.add(n.val);
            if (n.right) {
                n.right.val = 2 * n.val + 2;
                a.push(n.right);
            }
            if (n.left) {
                n.left.val = 2 * n.val + 1;
                a.push(n.left);
            }
        }
    }

    find(t) { // O(1)
        return this.s.has(t);
    }
};
```
```javascript [Recursion/Uint8Array]
class FindElements {
    s = new Uint8Array(1e4 + 1);

    constructor(r) { // O(n)
        const dfs = (n) => {
            this.s[n.val] = 1;
            if (n.left) {
                n.left.val = 2 * n.val + 1;
                dfs(n.left);
            }
            if (n.right) {
                n.right.val = 2 * n.val + 2;
                dfs(n.right);
            }
        };
        r.val = 0;
        dfs(r);
    }

    find(t) { // O(1)
        return this.s[t] === 1;
    }
};
```
['Tree', 'Depth-First Search', 'Design', 'C', 'Python', 'C++', 'Java', 'TypeScript', 'Python3', 'JavaScript']