Find Bottom Left Tree Value - Leetcode Solution

Problem statement:

Given a binary tree, find the leftmost value in the last row of the tree.

Example:

Input: 2 /
1 3

Output: 1

Explanation: The leftmost value in the last row is 1.

Solution:

The problem requires us to find the leftmost value in the last row of the binary tree. We can solve this problem by doing a level-order traversal of the binary tree. We can keep track of the last node on each level, and when we finish traversing the tree, we can return the value of the last node on the last level, which will be the leftmost value in the last row.

1. We first create a queue to hold the nodes to be processed. We also create a variable leftmost to hold the leftmost value on the last row.

2. We add the root node to the queue.

3. We start a loop that continues until the queue is empty.

4. In each iteration, we dequeue a node from the queue and assign its value to the leftmost variable.

5. We then add the children of the dequeued node to the queue, if they are not null.

6. At the end of the loop, we return the value of the leftmost variable, which will be the leftmost value on the last row.

Code:

Here is the code to solve the problem:

class Solution {
public:
    int findBottomLeftValue(TreeNode* root) {
        queue<TreeNode*> q;
        q.push(root);
        int leftmost;
        while (!q.empty()) {
            int size = q.size();
            for (int i = 0; i < size; i++) {
                TreeNode* node = q.front();
                q.pop();
                if (i == 0) leftmost = node->val;
                if (node->left) q.push(node->left);
                if (node->right) q.push(node->right);
            }
        }
        return leftmost;
    }
};

Time Complexity:

Since we are traversing all the nodes once, the time complexity of the algorithm is O(n), where n is the number of nodes in the binary tree.

Space Complexity:

The space complexity of the algorithm is O(w), where w is the maximum width of the binary tree. This is because, at any point in time, the queue will have at most w nodes, where w is the width of the binary tree. In the worst case, when the binary tree is a complete binary tree, the width is (n+1)/2, where n is the number of nodes in the binary tree. Hence, the space complexity is O(n/2) or O(n).

1