Find Bottom Left Tree Value - Practice Coding Problems

Find Bottom Left Tree Value - Problem

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

You need to find the value of the leftmost node in the bottom-most level of the tree. If there are multiple nodes at the same level, return the leftmost one.

Note: The tree is guaranteed to be non-empty.

Input & Output

Example 1 — Standard Tree

$ Input: root = [2,1,3,4,null,5,6,null,null,7]

› Output: 7

💡 Note: The bottom level has one node: 7. This is the leftmost (and only) value in the last row.

Example 2 — Multiple Bottom Nodes

$ Input: root = [1,2,3,4,null,5,6]

› Output: 4

💡 Note: The bottom level has nodes [4,5,6]. The leftmost value is 4.

Example 3 — Single Node

$ Input: root = [1]

› Output: 1

💡 Note: Only one node exists, so it's the leftmost value in the last (and only) row.

Constraints

The number of nodes in the tree is in the range [1, 10⁴]
-2³¹ ≤ Node.val ≤ 2³¹ - 1

Visualization

Tap to expand

Understanding the Visualization

Input Tree

Binary tree with multiple levels

Identify Bottom Level

Find the deepest level in the tree

Find Leftmost

Return leftmost value from bottom level

Key Takeaway

🎯 Key Insight: Use BFS to process the tree level by level - the first node visited at each level is automatically the leftmost

Asked in

G Google 15 a Amazon 12 M Microsoft 10 Apple 8

The key insight is to find the leftmost node in the bottom-most level of the tree. The BFS approach is optimal as it processes nodes level by level, naturally identifying the first (leftmost) node at each level. Time: O(n), Space: O(w) where w is maximum tree width.

Common Approaches

Approach	Time	Space	Notes
✓ Level-Order Traversal (BFS)	O(n)	O(w)	Use BFS to process tree level by level, keeping first node of each level
DFS with Level Tracking	O(n)	O(h)	Use DFS to visit all nodes while tracking depth and leftmost value

Level-Order Traversal (BFS) — Algorithm Steps

Step 1: Initialize queue with root node
Step 2: Process each level completely, tracking leftmost node
Step 3: Continue until queue is empty
Step 4: Return the leftmost value from the last processed level

Visualization

Tap to expand

Step-by-Step Walkthrough

Level 0

Process root level, leftmost is 2

Level 1

Process children level, leftmost is 1

Level 2

Process grandchildren level, leftmost is 4

Level 3

Process deepest level, leftmost is 7

Code -

solution.c — C

#include <stdio.h>
#include <stdlib.h>
#include <string.h>

struct TreeNode {
    int val;
    struct TreeNode* left;
    struct TreeNode* right;
};

struct Queue {
    struct TreeNode** nodes;
    int front, rear, size, capacity;
};

struct Queue* createQueue(int capacity) {
    struct Queue* q = (struct Queue*)malloc(sizeof(struct Queue));
    q->nodes = (struct TreeNode**)malloc(capacity * sizeof(struct TreeNode*));
    q->front = q->size = 0;
    q->rear = capacity - 1;
    q->capacity = capacity;
    return q;
}

int isEmpty(struct Queue* q) { return q->size == 0; }
int isFull(struct Queue* q) { return q->size == q->capacity; }

void enqueue(struct Queue* q, struct TreeNode* node) {
    if (isFull(q)) return;
    q->rear = (q->rear + 1) % q->capacity;
    q->nodes[q->rear] = node;
    q->size++;
}

struct TreeNode* dequeue(struct Queue* q) {
    if (isEmpty(q)) return NULL;
    struct TreeNode* node = q->nodes[q->front];
    q->front = (q->front + 1) % q->capacity;
    q->size--;
    return node;
}

int solution(struct TreeNode* root) {
    if (!root) return 0;
    
    struct Queue* queue = createQueue(1000);
    enqueue(queue, root);
    int leftmostVal = root->val;
    
    while (!isEmpty(queue)) {
        int levelSize = queue->size;
        
        for (int i = 0; i < levelSize; i++) {
            struct TreeNode* node = dequeue(queue);
            
            // First node in this level is the leftmost
            if (i == 0) {
                leftmostVal = node->val;
            }
            
            if (node->left) enqueue(queue, node->left);
            if (node->right) enqueue(queue, node->right);
        }
    }
    
    free(queue->nodes);
    free(queue);
    return leftmostVal;
}

struct TreeNode* createNode(int val) {
    struct TreeNode* node = (struct TreeNode*)malloc(sizeof(struct TreeNode));
    node->val = val;
    node->left = NULL;
    node->right = NULL;
    return node;
}

// Simple tree building for demonstration
struct TreeNode* buildSimpleTree() {
    struct TreeNode* root = createNode(2);
    root->left = createNode(1);
    root->right = createNode(3);
    root->left->left = createNode(4);
    root->right->left = createNode(5);
    root->right->right = createNode(6);
    root->right->left->left = createNode(7);
    return root;
}

int main() {
    // For demo purposes, create a sample tree
    struct TreeNode* root = buildSimpleTree();
    int result = solution(root);
    printf("%d\n", result);
    return 0;
}

Time & Space Complexity

Time Complexity

⏱️

O(n)

Must visit every node to ensure we reach the bottom level

✓ Linear Growth

Space Complexity

O(w)

Queue stores at most w nodes where w is maximum width of tree

✓ Linear Space

180.0K Views

Medium Frequency

~15 min Avg. Time

2.2K Likes

Ln 1, Col 1

Smart Actions

💡 Explanation

AI Ready

💡 Suggestion Tab to accept Esc to dismiss

// Output will appear here after running code

Code Editor Closed

Click the red button to reopen

Input & Output

Constraints

Visualization

Related Problems

Common Approaches

Level-Order Traversal (BFS) — Algorithm Steps

Visualization

Code -

Time & Space Complexity

Select Compiler