Bottom Right Value

Return the value of the bottom-most, right-most node — that is, the last node visited in a breadth-first (level-order) traversal. Assume a non-empty tree.

bottomRightValue(root)

Input format: level-order with x for missing children.

Examples

3 9 20 x x 15 7   // → 7
1 2 3 4           // → 4
1 2 x 3           // → 3

Walkthrough

Thinking it through

"Bottom-most, right-most" bundles two conditions: among the nodes on the deepest level, pick the one furthest right. Answering this with a purely depth-first recursive approach is awkward — DFS doesn't naturally track "deepest level overall" or "rightmost on that level" without extra bookkeeping.

Reframing around breadth-first order

Breadth-first traversal visits nodes in exactly the order that matters: level 0 completely, then level 1 (left to right), then level 2, and so on. Whichever node gets visited last overall is on the deepest level with any nodes (BFS doesn't move to a new level until the current one is exhausted) and is the rightmost on that level (BFS visits left to right within a level).

Building the algorithm

Run a standard BFS — queue seeded with the root, dequeue, enqueue children left-then-right — but instead of collecting values into a list, just overwrite a single "most recent value" variable every time you dequeue a node. Whatever's left in that variable when the queue empties is the bottom-most, right-most value.

Why this is a small, elegant reuse of plain BFS

No new traversal technique needed — just noticing that the last item BFS produces has special meaning here. Before reaching for extra bookkeeping, check whether the plain traversal order already encodes the answer you need.

Cost

Every node is enqueued and dequeued once, so work is proportional to the number of nodes, and the queue holds at most as many nodes as the tree's widest level.

main.py

Auto-saved

Console

Press Run to execute your code, or Submit to test and complete this problem.