Level Order Traversal (BFS) Beats 100% C++ | Explanation
\n\n# Intuition\nThe problem asks to find the leftmost value in the bottom row of a binary tree. We can use a level order traversal approach to traverse the tre
![Screenshot (234).png](https://assets.leetcode.com/users/images/7bdff1e3-e97b-4411-8736-62de404c20af_1709087984.371428.png)\n\n# Intuition\nThe problem asks to find the leftmost value in the bottom row of a binary tree. We can use a level order traversal approach to traverse the tree level by level and return the leftmost value of the last level.\n\n# Approach\nThe approach involves using a queue for level order traversal. We traverse the tree level by level, keeping track of the leftmost value encountered at each level. At the end of the traversal, we return the leftmost value of the last level.\n\n1. **Level Order Traversal**:\n   - Utilizes breadth-first search (BFS) to traverse the binary tree level by level, ensuring systematic exploration from top to bottom and left to right.\n\n2. **Using a Queue**:\n   - Implements a queue data structure to manage the order of node exploration, enabling FIFO (First-In-First-Out) traversal.\n\n3. **Tracking the Leftmost Value**:\n   - Maintains the leftmost value encountered at each level, initially setting it to the value of the root node.\n\n4. **Updating Leftmost Value**:\n   - Updates the leftmost value whenever a new level is encountered, ensuring it represents the value of the leftmost node at the current level.\n\n5. **Completing Traversal**:\n   - Continues traversal until all nodes have been visited, ensuring systematic coverage of the entire binary tree.\n\n# Complexity\n- Time complexity: $$O(n)$$, where $$n$$ is the number of nodes in the binary tree.\n- Space complexity: $$O(w)$$, where $$w$$ is the maximum width of the tree (number of nodes in the last level).\n\n# Code\n```cpp\n/**\n * Definition for a binary tree node.\n * struct TreeNode {\n *     int val;\n *     TreeNode *left;\n *     TreeNode *right;\n *     TreeNode() : val(0), left(nullptr), right(nullptr) {}\n *     TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}\n *     TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}\n * };\n */\nclass Solution {\npublic:\n    int levelOrderTraversal(TreeNode* root)\n    {\n        queue<TreeNode*> q;\n        q.push(root);\n        q.push(NULL);\n\n        int newLevelFlag = 1;\n        int leftMost = q.front()->val;\n\n        while(!q.empty())\n        {\n            TreeNode* temp = q.front();\n            q.pop();\n\n            if(temp==NULL)\n            {\n                if(!q.empty())\n                    q.push(NULL);\n                newLevelFlag = 1;// NEW LEVEL IS ENCOUNTERED\n            }\n            else\n            {\n                //cout<<temp->data<<" ";\n                // Processing the first element only\n                if(newLevelFlag)\n                    leftMost = temp->val;\n                if(temp->left)\n                    q.push(temp->left);\n                if(temp->right)\n                    q.push(temp->right);\n                newLevelFlag=0;// FIRST ELEMENT \n                                //OF NEW LEVEL IS ENCOUNTERD\n            }\n\n        }\n        return leftMost;\n    }\n\n    int findBottomLeftValue(TreeNode* root) {\n        return levelOrderTraversal(root);\n    }\n};\n```
['Tree', 'Breadth-First Search', 'Binary Tree', 'C++']