algoadvance

Leetcode 513. Find Bottom Left Tree Value

Problem Statement

You are given the root of a binary tree, and you need to find the leftmost value in the last row of the tree.

Clarifying Questions

1. What is the range of values for the nodes in the tree?
   • Node values are within the range of signed 32-bit integers.
2. Can the tree be empty? If yes, what should be the return value?
   • For this problem, we can assume the tree is not empty, as the problem guarantees that the binary tree is non-empty.
3. Are there any particular constraints on the size of the tree?
   • There are no specific constraints on the tree size, other than the practical limits of memory and processing time.

Strategy

To solve this problem, we can use a level-order traversal (BFS) approach. Here is the step-by-step strategy:

1. Understand Tree Traversal: The idea is to traverse the tree level by level, using a queue to keep track of nodes at each level.

2. Track Last Level: While traversing, we keep track of the first node in each level, ensuring that at the end of the traversal, the last recorded node’s value is the leftmost value of the last level.

3. Use BFS: Breadth-First Search (BFS) is well suited for this problem as it explores the nodes level by level.

Code

Here’s how you can implement this in C++:

#include <iostream>
#include <queue>
using namespace std;

// 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) {}
};

class Solution {
public:
    int findBottomLeftValue(TreeNode* root) {
        if (root == nullptr) {
            return -1; // as per the assumption tree is non-empty
        }

        queue<TreeNode*> q;
        q.push(root);
        int bottomLeftValue = root->val;

        while (!q.empty()) {
            int levelSize = q.size();
            for (int i = 0; i < levelSize; ++i) {
                TreeNode* currentNode = q.front();
                q.pop();

                // Capture the first node of this level (leftmost)
                if (i == 0) {
                    bottomLeftValue = currentNode->val;
                }
                
                // add children to the queue for next level
                if (currentNode->left != nullptr) {
                    q.push(currentNode->left);
                }
                if (currentNode->right != nullptr) {
                    q.push(currentNode->right);
                }
            }
        }

        return bottomLeftValue;
    }
};

int main() {
    // Example usage:
    TreeNode* root = new TreeNode(1);
    root->left = new TreeNode(2);
    root->right = new TreeNode(3);
    root->left->left = new TreeNode(4);
    root->right->left = new TreeNode(5);
    root->right->right = new TreeNode(6);
    root->right->left->left = new TreeNode(7);

    Solution solution;
    cout << "Bottom left value: " << solution.findBottomLeftValue(root) << endl; // Outputs 7

    // Add code to delete allocated nodes to avoid memory leaks if necessary.
}

Time Complexity

• Time Complexity: O(N), where N is the number of nodes in the tree. We visit each node exactly once.

• Space Complexity: O(M), where M is the maximum number of nodes at any level in the tree. This is because we use a queue to store the nodes of the current level being traversed, which can be up to M nodes.

This strategic approach ensures that we efficiently find the leftmost value in the last row of the binary tree using BFS.

Cut your prep time in half and DOMINATE your interview with AlgoAdvance AI

• Got blindsided by a question you didn’t expect?

• Spend too much time studying?

• Or simply don’t have the time to go over all 3000 questions?