Find Bottom Left Tree Value
Medium · Trees · Tree · Depth-First Search · Breadth-First Search · Binary Tree
Problem
Given the root of a binary tree, return the leftmost value on its last (deepest) row.
The deepest row is the one farthest from the root, and its leftmost value is the first one when the row is read left to right. That node is not necessarily in the root's left subtree.
Examples
Input: root = [3,9,4,null,null,6,8,null,2] Output: 2
The deepest row contains only 2, the right child of 6, deep in the right subtree.
Input: root = [7,1,5] Output: 1
The last row is [1,5], and 1 is leftmost.
Constraints
- The number of nodes is in the range [1, 10^4]
- -2^31 <= Node.val <= 2^31 - 1
Approaches
- Baseline: search each row from the root — time O(n · h), space O(h)
Follow-up
The same walk answers other questions about rows: the sum of the deepest row, or which row has the largest sum. Those are the use cases.
Related problems
Start free on Cariara · Coding problems · System design studio
