Find Bottom Left Tree Value

Medium
1921.

Find Bottom Left Tree Value

Find Bottom Left Tree Value is a medium coding problem on depth-first search, breadth-first search and trees, asked in Amazon, Google and Microsoft interviews.

Given the root of a non-empty binary tree, return the value of the leftmost node in its last row — among the nodes at the greatest depth, the one furthest to the left.

Example 1

Input
root = [2,1,3]
Output
1
Explanation
The last row is 1, 3; its leftmost value is 1.

Example 2

Input
root = [1,2,3,4,null,5,6,null,null,7]
Output
7
Explanation
The deepest row holds only 7, the left child of 5.

Example 3

Input
root = [1,null,2,3,4]
Output
3
Explanation
The bottom row is 3, 4 — both in the root's right subtree. The leftmost node of the last row need not be a left child of anything near the root.

Constraints

  • The number of nodes in the tree is in the range [1, 10^4]
  • -2^31 <= Node.val <= 2^31 - 1
Write your solution here. Running it against the tests needs a free account — what you type comes with you.Sign in to run
/**
 * Definition for a binary tree node (provided by the judge — do not redefine it):
 * function TreeNode(val, left, right) {
 *     this.val = (val===undefined ? 0 : val)
 *     this.left = (left===undefined ? null : left)
 *     this.right = (right===undefined ? null : right)
 * }
 */
/**
 * @param {TreeNode} root
 * @return {number}
 */
var findBottomLeftValue = function(root) {
    // Write your code here
    
};

Sign in to run your own test cases

Sign in

Find Bottom Left Tree Value — Solution in Python, Java & C++

Find Bottom Left Tree Value solution explained: step-by-step approach, complexity and code in Python, Java, C++ and JavaScript. A medium problem.

Find Bottom Left Tree Value is a medium coding problem on depth-first search, breadth-first search and trees, asked in Amazon, Google and Microsoft interviews.

Problem statement

Given the root of a non-empty binary tree, return the value of the leftmost node in its last row — among the nodes at the greatest depth, the one furthest to the left.

Example 1

Input: root = [2,1,3]
Output: 1
Explanation: The last row is 1, 3; its leftmost value is 1.

Example 2

Input: root = [1,2,3,4,null,5,6,null,null,7]
Output: 7
Explanation: The deepest row holds only 7, the left child of 5.

Example 3

Input: root = [1,null,2,3,4]
Output: 3
Explanation: The bottom row is 3, 4 — both in the root's right subtree. The leftmost node of the last row need not be a left child of anything near the root.

Constraints

  • The number of nodes in the tree is in the range [1, 10^4]
  • -2^31 <= Node.val <= 2^31 - 1

Hints for Find Bottom Left Tree Value

  1. Hint 1

    A level-order (breadth-first) walk visits the tree row by row, each row from left to right.

  2. Hint 2

    The first node of the last row is the answer — so remember the first value of every row; the last one remembered wins.

  3. Hint 3

    A neat variant: walk each row right to left (enqueue the right child before the left). Then the very last node dequeued is the answer.

How to solve Find Bottom Left Tree Value

Breadth-first search processes the tree one row at a time. If each row is processed from right to left, the final node taken off the queue lies in the deepest row and is the leftmost one there.

Approach

  1. Put the root in a queue.
  2. Repeatedly dequeue a node, record its value, then enqueue its right child and then its left child (when present).
  3. When the queue is empty, the last recorded value is the answer.

Why it works

BFS dequeues all nodes of one depth before any node of the next depth, so the last node dequeued is in the deepest row. Within a row, enqueuing right before left makes the row come out right to left, so the last node of the deepest row is its leftmost.

Complexity

  • Time — O(n)
  • Space — O(w), where w is the widest row — O(n) at worst

Pitfalls

  • The answer is the leftmost node of the deepest row, not the deepest node reached by always going left.
  • Values span the whole 32-bit range; never use a value such as 0 or -1 as a 'not found' marker.

Reference solution

Python

from collections import deque
from typing import Optional

def findBottomLeftValue(root: Optional[TreeNode]) -> int:
    queue = deque([root])
    ans = root.val
    while queue:
        node = queue.popleft()
        ans = node.val
        if node.right is not None:
            queue.append(node.right)
        if node.left is not None:
            queue.append(node.left)
    return ans

Java

public static int findBottomLeftValue(TreeNode root) {
    ArrayDeque<TreeNode> queue = new ArrayDeque<>();
    queue.add(root);
    int ans = root.val;
    while (!queue.isEmpty()) {
        TreeNode node = queue.poll();
        ans = node.val;
        if (node.right != null) queue.add(node.right);
        if (node.left != null) queue.add(node.left);
    }
    return ans;
}

C++

int findBottomLeftValue(TreeNode* root) {
    queue<TreeNode*> q;
    q.push(root);
    int ans = root->val;
    while (!q.empty()) {
        TreeNode* node = q.front();
        q.pop();
        ans = node->val;
        if (node->right) q.push(node->right);
        if (node->left) q.push(node->left);
    }
    return ans;
}

JavaScript

var findBottomLeftValue = function(root) {
    var queue = [root], head = 0, ans = root.val;
    while (head < queue.length) {
        var node = queue[head++];
        ans = node.val;
        if (node.right !== null) queue.push(node.right);
        if (node.left !== null) queue.push(node.left);
    }
    return ans;
};

Also on the editorial tab: C, C#, Go, Kotlin, PHP, Ruby, Rust, Swift, TypeScript.

All 201 depth-first search problems · the whole catalogue

Learn the technique: Depth-First Search (DFS) · Breadth-First Search (BFS)