Problem Overview

Continuing with binary tree traversal problems. This is problem 513: Find the value of the bottom-left node in a binary tree.

Problem Statement

Given the root of a binary tree, return the value of the bottommost-leftmost node in the tree. The tree has at least one node.

Example 1:

Input: root = [2, 1, 3]
Output: 1

Example 2:

Input: [1, 2, 3, 4, null, 5, 6, null, null, 7]
Output: 7

Constraints:

Number of nodes: [1, 10^4]
-2^31 <= Node.val <= 2^31 - 1

Solution Approach

Approach 1: Recursive DFS with Depth Tracking

The key insight is that we need to track the maximum depth encountered while traversing. The first node found at the deepest level will naturally be the leftmost node due to our traversal order.

1. Traversal order: Pre-order (root → left → right). Since we traverse left before right, when we discover a new maximum depth, that node must be the leftmost node at that depth.
2. Key parameters:
   • Current node (TreeNode*)
   • Current depth (int, passed by value for automatic backtracking)
   • Result reference (int&, passed by reference to update the final answer)
3. Base case: When encountering a leaf node, compare its depth with the tracked maximum depth. If greater, update both the max depth and the result value.

/**
 * 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 deepestLevel = 1;
    
    void explore(TreeNode* node, int level, int& answer) {
        if (!node->left && !node->right) {
            if (level > deepestLevel) {
                deepestLevel = level;
                answer = node->val;
            }
            return;
        }
        
        if (node->left) {
            explore(node->left, level + 1, answer);
        }
        if (node->right) {
            explore(node->right, level + 1, answer);
        }
    }
    
    int findBottomLeftValue(TreeNode* root) {
        int answer = root->val;
        explore(root, 1, answer);
        return answer;
    }
};

Approach 2: Iterative BFS (Level-order Traversal)

Using a queue to perform level-order traversal, we process nodes layer by layer. For each level, we record the first node's value. Since we process levels from top to bottom, the last recorded value will be from the bottommost level.

/**
 * 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) {
        int leftmostValue = root->val;
        std::queue<TreeNode*> nodes;
        nodes.push(root);
        
        while (!nodes.empty()) {
            int levelSize = nodes.size();
            
            for (int i = 0; i < levelSize; i++) {
                TreeNode* current = nodes.front();
                nodes.pop();
                
                if (i == 0) {
                    leftmostValue = current->val;
                }
                
                if (current->left) nodes.push(current->left);
                if (current->right) nodes.push(current->right);
            }
        }
        
        return leftmostValue;
    }
};

Complexity Analysis

Recursive approach:

• Time: O(n) - visiting each node once
• Space: O(h) - recursion stack, where h is the tree height

Iterative BFS approach:

• Time: O(n) - visiting each node once
• Space: O(w) - queue size, where w is the maximum width of the tree