How do I practice coding and algorithm questions?

Use PracHub's coding console to write, test, and debug your solutions in Python or JavaScript. View hints, test against sample inputs, and compare with official solutions.

What difficulty level is this coding question?

This is a easy difficulty Coding & Algorithms question, commonly asked during Technical Screen rounds at Google.

What role is this question designed for?

This question is commonly asked for Software Engineer candidates at Google during technical interviews.

Find right-side view of binary tree | Google Coding Question

Find right-side view of binary tree

Company: Google

Role: Software Engineer

Category: Coding & Algorithms

Difficulty: easy

Interview Round: Technical Screen

You are given the root of a binary tree. From the **right side** of the tree, at each depth you can see exactly one node: the rightmost node at that depth. Write a function that returns a list of the values of the nodes visible when looking at the tree from the right side, ordered from **top to bottom**. --- ### Function Signature (one possible form) ```text rightSideView(root: TreeNode) -> List[int] ``` Where `TreeNode` is defined as: ```text class TreeNode { int val; TreeNode left; TreeNode right; } ``` --- ### Example Consider this binary tree: ```text 1 / \ 2 3 \ \ 5 4 ``` The right-side view is: ```text [1, 3, 4] ``` Explain the algorithm you would use, including its time and space complexity. You may use either breadth-first search (BFS) or depth-first search (DFS).

Quick Answer: This question evaluates understanding of binary tree structures and traversal techniques, specifically reasoning about the right-side view by depth, along with the ability to analyze time and space complexity.

You are given the root of a binary tree, encoded as a level-order array (LeetCode style) where `null` marks a missing child. Standing on the right side of the tree, at each depth you can see exactly one node: the rightmost node at that depth. Return the list of node values visible from the right side, ordered from top (root) to bottom. The input array is the level-order serialization of the tree. For example, `[1, 2, 3, null, 5, null, 4]` encodes: ``` 1 / \ 2 3 \ \ 5 4 ``` whose right-side view is `[1, 3, 4]`. Approach: run a breadth-first (level-order) traversal. For each level, the last node dequeued is the rightmost visible node — append its value to the answer. (A DFS that visits right children before left children and records the first node seen at each depth works equally well.) Both run in O(n) time over n nodes. Implement `rightSideView(levelOrder)` which takes the level-order array and returns the right-side view as a list/array of integers.

Constraints

The number of nodes is in the range [0, 10^4].
-10^4 <= Node.val <= 10^4
The input is a valid level-order serialization where `null`/`None` marks a missing child.
An empty input array represents an empty tree and should return an empty list.

Examples

Input: ([1, 2, 3, None, 5, None, 4],)

Expected Output: [1, 3, 4]

Explanation: The example tree. Depth 0 sees 1, depth 1 sees the rightmost node 3, depth 2 sees the rightmost node 4 (node 5 is hidden behind 4).

Input: ([1, 2, 3, 4],)

Expected Output: [1, 3, 4]

Explanation: Tree with root 1, children 2 and 3, and 4 as the left child of 2. Rightmost at each depth: 1, then 3, then 4 (the only node at depth 2).

Input: ([],)

Expected Output: []

Explanation: Empty tree edge case — nothing is visible, so the right-side view is empty.

Input: ([7],)

Expected Output: [7]

Explanation: Single-node tree; the only node is the rightmost at depth 0.

Input: ([1, 2, None, 3, None, 4],)

Expected Output: [1, 2, 3, 4]

Explanation: A left-skewed tree (every node has only a left child). With nothing on the right, each level's only node is visible: 1, 2, 3, 4.

Input: ([1, None, 2, None, 3],)

Expected Output: [1, 2, 3]

Explanation: A right-skewed tree; each level's single node is the rightmost: 1, 2, 3.

Input: ([-5, -10, -3, None, -8],)

Expected Output: [-5, -3, -8]

Explanation: Negative values. Depth 0: -5; depth 1 rightmost: -3; depth 2 rightmost: -8 (the right child of -10).

Hints

A level-order (BFS) traversal naturally groups nodes by depth — the last node you process at each level is exactly the one visible from the right.
Process the queue level by level: record the current queue size, dequeue that many nodes, and append the value of the final node in the batch to your answer.
Alternatively, run a DFS that recurses into the RIGHT child before the LEFT child; the first node you reach at each new depth is the right-side node.
Don't forget the empty-tree case: an empty input must return an empty list.

Quick Overview

This question evaluates understanding of binary tree structures and traversal techniques, specifically reasoning about the right-side view by depth, along with the ability to analyze time and space complexity.