45. Binary Tree Right Side View

MediumTree Binary Tree BFS DFS

Imagine standing to the right of a binary tree and looking at it. At each depth you can see exactly one node: the rightmost one on that level. Given the root, return the values you can see, ordered from the top level to the bottom.

Note that the visible node is not always a right child: if a level has nothing further right, a left-side node shows through.

Example 1

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

Explanation: On the last level only 6 exists, so it is visible even though it hangs on the far left.

Example 2

Input: root = [1,null,3]
Output: [1,3]

Example 3

Input: root = []
Output: []

Constraints

The number of nodes is in the range [0, 100]
-100 <= Node.val <= 100

💡 Hint 1

Group the nodes by depth. Which node of each group is the one you see?

💡 Hint 2

A level-order traversal gives you each level in left-to-right order; keep the last node of every level.

💡 Hint 3

Alternatively, DFS visiting the right child before the left: the first node you reach at each new depth is the visible one.

Try it yourself first ✎

Solutions stick better after a real attempt. Peek when you're ready.

Approach

Do a level-order traversal (BFS). Process the queue one level at a time, using the queue's size at the start of the level to know how many nodes belong to it. The last node dequeued in each level is the rightmost one, so append its value to the answer. A right-first DFS that records the first value seen at each new depth is an equally good alternative.

Time O(n)Space O(w), where w is the widest level

function rightSideView(root) {
  const view = [];
  let level = root ? [root] : [];
  while (level.length) {
    view.push(level[level.length - 1].val);
    const next = [];
    for (const node of level) {
      if (node.left) next.push(node.left);
      if (node.right) next.push(node.right);
    }
    level = next;
  }
  return view;
}

class Solution {
    public List<Integer> rightSideView(TreeNode root) {
        List<Integer> view = new ArrayList<>();
        if (root == null) return view;
        Deque<TreeNode> queue = new ArrayDeque<>();
        queue.add(root);
        while (!queue.isEmpty()) {
            int size = queue.size();
            for (int i = 0; i < size; i++) {
                TreeNode node = queue.poll();
                if (i == size - 1) view.add(node.val);
                if (node.left != null) queue.add(node.left);
                if (node.right != null) queue.add(node.right);
            }
        }
        return view;
    }
}

/**
 * Definition for a binary tree node (provided):
 * function TreeNode(val, left, right) { this.val = val ?? 0; this.left = left ?? null; this.right = right ?? null; }
 *
 * @param {TreeNode} root
 * @return {number[]}
 */
function rightSideView(root) {

}

Ctrl/⌘ + ' run · Ctrl/⌘ + Enter submit