Binary Tree Right Side View

MediumTree Binary Tree BFS DFS

A hotel lobby has a sculpture of lanterns hung in the shape of a binary tree, one level below another. A guest standing at the far right of the lobby sees exactly one lantern per level: the rightmost lantern on that level, which hides the others behind it.

Given the root of the tree, return the values of the visible lanterns from the top level to the bottom. The visible lantern is not always a right child: if nothing on a level hangs further right, a lantern from a left branch shows through.

Example 1

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

Explanation: On the last level only 3 exists, so it is visible even though it hangs from the left branch.

Example 2

Input: root = [10,null,12,11]
Output: [10,12,11]

Explanation: Each level has a single lantern, so all of them are visible.

Example 3

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

Explanation: In a full tree, the guest sees the rightmost lantern of each level.

Constraints

The tree has at most 100 nodes.
Node values are integers from -1000 to 1000.

💡 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