Right/Left View of Binary Tree

Medium

Last node of each level

Problem

Return the right view (and/or left view) of a binary tree: the last (or first) node of each level.

In simple words

Look at each level from the side: keep the last node you'd see on every row.

The idea

Traverse level by level and keep the final node of each level for the right view, or the first for the left view. A DFS visiting right before left records the same thing the first time it reaches each new depth.

The trick

BFS: take the last node popped per level.
DFS: go right first and record when depth equals the results length.

←→stepspaceplay

1/5

Optimal

timeO(n)spaceO(n)

Fix the level width up front.

1const q = [root], out = [];2while (q.length) {3  const level = [];4  for (let n = q.length; n > 0; n--) {5    const node = q.shift();6    level.push(node.val);7    if (node.left) q.push(node.left);8    if (node.right) q.push(node.right);9  }10  out.push(level);11}

Input

nodes: 6, 5 edges

Memory

levels: —

Output

answer: —

Check yourself

3 quick questions about this walkthrough. A wrong answer costs nothing.

Examples

Example 1

Input:: tree = [1,2,3,null,5,null,4]
Output:: [1, 3, 4]
Explanation:: The rightmost node on each level → 1,3,4.

Example 2

Input:: tree = [1,2,3]
Output:: [1, 3]
Explanation:: 1 then 3.

Example 3

Input:: tree = [1]
Output:: [1]
Explanation:: Just the root.

Practice this problem:LeetCode(opens in a new tab)Search GeeksforGeeks(opens in a new tab)

Finished the walkthrough? Add it to your streak.