DFS+bitset vs BFS||C++ Py3 beats 100%
IntuitionDFS+ bitsetUse DFS to traverse the binary tree with bitset as a container for marking the value of node is seen instead of a hash table.BFS is also mad
# Intuition
<!-- Describe your first thoughts on how to solve this problem. -->
DFS+ bitset
Use DFS to traverse the binary tree with bitset as a container for marking the value of node is seen instead of a hash table.
BFS is also made for C++ & Python
# Approach
<!-- Describe your approach to solving the problem. -->
1. Declare `bitset<1048576> hasX = 0`, since `1048576=2**20`
2. Let `root` be member variable
3. In constructor call `dfs(root, 0)`
4. The destuctor resets `hasX=0`, since `hasX` is declared as a global variable
5. Define the method dfs as follows
```
void dfs(TreeNode* root, int x) {
    if (!root) // leaf node
        return;
    root->val = x;
    hasX[x] = 1; // mark as seen
    dfs(root->left, 2 * x + 1); // left subtree
    dfs(root->right, 2 * x + 2); // right subtree
}
```
6. the method `find` just returns `hasX[target]`
7. BFS is made by using `std::queue`; it needs only to replace dfs by bfs in the constructor. 
# Complexity
- Time complexity:
<!-- Add your time complexity here, e.g. $$O(n)$$ -->
$O(n)$
- Space complexity:
<!-- Add your space complexity here, e.g. $$O(n)$$ -->
$O(n)$
# Code||C++ 0ms beats 100%
```cpp []
/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode() : val(0), left(nullptr), right(nullptr) {}
 *     TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
 *     TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left),
 * right(right) {}
 * };
 */
bitset<1048576> hasX = 0; // 2097152=2**21
class FindElements {
public:
    TreeNode* root;

    FindElements(TreeNode* root) { dfs(root, 0); }
    ~FindElements() { hasX = 0; }
    void dfs(TreeNode* root, int x) {
        if (!root)
            return;
        root->val = x;
        hasX[x] = 1;
        dfs(root->left, 2 * x + 1);
        dfs(root->right, 2 * x + 2);
    }

    bool find(int target) { return hasX[target]; }
};

/**
 * Your FindElements object will be instantiated and called as such:
 * FindElements* obj = new FindElements(root);
 * bool param_1 = obj->find(target);
 */
```
# Codes for Python & C++ BFS 0ms|Just replace dfs by bfs in C++
```Python []
# Definition for a binary tree node.
# class TreeNode:
#     def __init__(self, val=0, left=None, right=None):
#         self.val = val
#         self.left = left
#         self.right = right
class FindElements:

    def __init__(self, root: Optional[TreeNode]):
        self.hasX=set()
        def bfs(root):
            q=deque()
            root.val=0
            q.append(root)

            while q:
                node=q.popleft()
                x=node.val
                self.hasX.add(x)

                if node.left:
                    node.left.val=2*x+1
                    q.append(node.left)
                if node.right:
                    node.right.val=2*x+2
                    q.append(node.right)
        bfs(root)
        

    def find(self, target: int) -> bool:
        return target in self.hasX
        


# Your FindElements object will be instantiated and called as such:
# obj = FindElements(root)
# param_1 = obj.find(target)
```
```cpp [C++ BFS]
    void bfs(TreeNode* root) {
        queue<TreeNode*> q;
        root->val = 0;
        q.push(root);

        while (!q.empty()) {
            TreeNode* node = q.front();
            int x = node->val;
            hasX[x]=1;
            q.pop(); 
            
            if (node->left) {
                node->left->val = 2 * x + 1;
                q.push(node->left);
            }
            if (node->right) {
                node->right->val = 2 * x + 2;
                q.push(node->right);
            }
        }
    }
```
# DFS & BFS are frequently used to solve LC questions

Some Leetcode binary tree questions
[1457. Pseudo-Palindromic Paths in a Binary Tree](https://leetcode.com/problems/pseudo-palindromic-paths-in-a-binary-tree/solutions/4616431/dfs-bitset-parity-check-beats-100/)
[623. Add One Row to Tree](https://leetcode.com/problems/add-one-row-to-tree/solutions/5029368/recursive-iterative-dfs-vs-bfs-4ms-beats-98-32/)
[Please turn on English subtitles if necessary]
[https://youtu.be/53GEbY2e3JM?si=kX4HmDKz5Wq3fheN](https://youtu.be/53GEbY2e3JM?si=kX4HmDKz5Wq3fheN)
['Depth-First Search', 'Breadth-First Search', 'C++', 'Python3']