Binary Tree Right Side View

Med

#0187Time: O(N)Space: O(W)9 companies

Algorithms

Depth-First Search Breadth-First Search

Data structures

Tree Binary Tree

Companies

Accolite Flipkart Google J.P. Morgan

Prompt

Given the root of a binary tree, imagine yourself standing on the right side of it, return the values of the nodes you can see ordered from top to bottom.

Example 1:

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

Output: [1,3,4]

Explanation:

Example 2:

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

Output: [1,3,4,5]

Explanation:

Example 3:

Input: root = [1,null,3]

Output: [1,3]

Example 4:

Input: root = []

Output: []

Constraints:

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

Approaches

2 approaches with complexity analysis and trade-offs.

This approach uses Breadth-First Search (BFS) to traverse the tree level by level. For each level, the very last node that gets processed is the rightmost node. We can identify this node and add its value to our result list. This method is highly intuitive because the problem is defined in terms of levels, and BFS is the natural algorithm for level-by-level processing.

Algorithm

Create an empty list result to store the right side view.
If the root is null, return the empty list.
Create a Queue and add the root node to it.
Loop while the queue is not empty:
- Get the number of nodes at the current level, levelSize = queue.size().
- This levelSize is crucial as it defines the boundary for the current level.
- Loop levelSize times:
  - Dequeue a node, let's call it currentNode.
  - Check if this is the last node of the level. This can be determined if the loop index i is equal to levelSize - 1.
  - If it is the last node, add its value to the result list.
  - Enqueue the left child of currentNode if it exists.
  - Enqueue the right child of currentNode if it exists.
After the main loop finishes, return the result list.

Walkthrough

We can solve this problem using a standard level order traversal, which is implemented with a queue. The idea is to traverse the tree one level at a time. For each level, we want to find the rightmost node. When we process a level, we know exactly how many nodes are on that level (it's the size of the queue at the beginning of the level's processing). We can iterate through all nodes of the current level, and the last node we pull from the queue in that iteration will be the rightmost one. We add this node's value to our result list. We repeat this for all levels until the entire tree is traversed.

1/**2 * Definition for a binary tree node.3 * public class TreeNode {4 *     int val;5 *     TreeNode left;6 *     TreeNode right;7 *     TreeNode() {}8 *     TreeNode(int val) { this.val = val; }9 *     TreeNode(int val, TreeNode left, TreeNode right) {10 *         this.val = val;11 *         this.left = left;12 *         this.right = right;13 *     }14 * }15 */16class Solution {17    public List<Integer> rightSideView(TreeNode root) {18        List<Integer> result = new ArrayList<>();19        if (root == null) {20            return result;21        }22 23        Queue<TreeNode> queue = new LinkedList<>();24        queue.offer(root);25 26        while (!queue.isEmpty()) {27            int levelSize = queue.size();28            for (int i = 0; i < levelSize; i++) {29                TreeNode currentNode = queue.poll();30                // If it's the last node of the current level31                if (i == levelSize - 1) {32                    result.add(currentNode.val);33                }34                if (currentNode.left != null) {35                    queue.offer(currentNode.left);36                }37                if (currentNode.right != null) {38                    queue.offer(currentNode.right);39                }40            }41        }42        return result;43    }44}

Complexity

Time

O(N)

Space

O(W)

Trade-offs

Pros

It's a very direct and intuitive approach that maps well to the problem statement.
It works for any binary tree and correctly identifies the rightmost node at each level.
It can be more space-efficient than DFS for very deep and narrow (skewed) trees.

Cons

The space complexity can be significant for wide trees. In the worst case of a complete binary tree, the queue might need to store up to N/2 nodes, where N is the total number of nodes.

A more elegant and often more space-efficient approach uses Depth-First Search (DFS). The trick is to modify the standard pre-order traversal (Root-Left-Right) to a reverse pre-order traversal (Root-Right-Left). By visiting the right subtree first, we ensure that the first node we encounter at any given depth is the rightmost node at that level. We use the size of our result list to track the maximum depth visited so far.

Algorithm

Create an empty list result.
Call a recursive helper function, for example, dfs(node, level, result).
The initial call would be dfs(root, 0, result).
Inside the dfs function:
- If the current node is null, simply return.
- Check if the current level is equal to the size of the result list. If it is, this means we are visiting this level for the first time. Since we traverse the right side first, this node must be the rightmost one. Add node.val to result.
- Make a recursive call for the right child, incrementing the level: dfs(node.right, level + 1, result).
- Make a recursive call for the left child, incrementing the level: dfs(node.left, level + 1, result).
After the initial call returns, the result list will contain the right side view.

Walkthrough

This approach leverages recursion and a specific traversal order to solve the problem efficiently. We define a recursive function that takes the current node, its level (or depth), and the result list. The key idea is to traverse the right subtree of any node before its left subtree.

When our recursive function visits a node at a certain level, we check if we've seen this level before. We can do this by comparing the level with the current size of our result list. If level == result.size(), it means we're encountering a node at this depth for the first time. Because our traversal prioritizes the right side, this first-encountered node is guaranteed to be the rightmost node at that level. We add its value to the result list. For any subsequent nodes visited at the same level (which would be to the left of the one we just added), the condition level == result.size() will be false, so we won't add them. This elegantly builds the right-side view.

1/**2 * Definition for a binary tree node.3 * public class TreeNode {4 *     int val;5 *     TreeNode left;6 *     TreeNode right;7 *     TreeNode() {}8 *     TreeNode(int val) { this.val = val; }9 *     TreeNode(int val, TreeNode left, TreeNode right) {10 *         this.val = val;11 *         this.left = left;12 *         this.right = right;13 *     }14 * }15 */16class Solution {17    public List<Integer> rightSideView(TreeNode root) {18        List<Integer> result = new ArrayList<>();19        dfs(root, 0, result);20        return result;21    }22 23    private void dfs(TreeNode node, int level, List<Integer> result) {24        if (node == null) {25            return;26        }27        // If this is the first time we visit this level, it must be the rightmost node.28        if (level == result.size()) {29            result.add(node.val);30        }31        // Traverse right subtree first32        dfs(node.right, level + 1, result);33        // Then traverse left subtree34        dfs(node.left, level + 1, result);35    }36}

Complexity

Time

O(N)

Space

O(H)

Trade-offs

Pros

Very concise and elegant code.
Generally more space-efficient than BFS for balanced or complete binary trees, as its space complexity depends on the tree's height (O(log N)) rather than its width (O(N)).

Cons

The recursion depth can be large for skewed trees, potentially leading to a StackOverflowError for extremely deep trees. The worst-case space complexity is O(N) for a skewed tree.

Solutions

Solution

1/** * Definition for a binary tree node. * public class TreeNode { * int val; * TreeNode left; * TreeNode right; * TreeNode() {} * TreeNode(int val) { this.val = val; } * TreeNode(int val, TreeNode left, TreeNode right) { * this.val = val; * this.left = left; * this.right = right; * } * } */ class Solution { public List < Integer > rightSideView ( TreeNode root ) { List < Integer > ans = new ArrayList <>(); if ( root == null ) { return ans ; } Deque < TreeNode > q = new ArrayDeque <>(); q . offer ( root ); while (! q . isEmpty ()) { ans . add ( q . peekLast (). val ); for ( int n = q . size (); n > 0 ; -- n ) { TreeNode node = q . poll (); if ( node . left != null ) { q . offer ( node . left ); } if ( node . right != null ) { q . offer ( node . right ); } } } return ans ; } }

1/** * Definition for a binary tree node. * function TreeNode(val, left, right) { * this.val = (val===undefined ? 0 : val) * this.left = (left===undefined ? null : left) * this.right = (right===undefined ? null : right) * } */ /** * @param {TreeNode} root * @return {number[]} */ var rightSideView =2  function (root) {3    const ans = [];4    if (!root) {5      return ans;6    }7    const q = [root];8    while (q.length > 0) {9      ans.push(q[0].val);10      const nq = [];11      for (const { left, right } of q) {12        if (right) {13          nq.push(right);14        }15        if (left) {16          nq.push(left);17        }18      }19      q.length = 0;20      q.push(...nq);21    }22    return ans;23  };

1/** * Definition for a binary tree node. * struct TreeNode { * int val; * TreeNode *left; * TreeNode *right; * TreeNode() : val(0), left(nullptr), right(nullptr) {} * TreeNode(int x) : val(x), left(nullptr), right(nullptr) {} * TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {} * }; */ class Solution { public: vector < int > rightSideView ( TreeNode * root ) { vector < int > ans ; if ( ! root ) { return ans ; } queue < TreeNode *> q { { root } }; while ( ! q . empty ()) { ans . emplace_back ( q . back () -> val ); for ( int n = q . size (); n ; -- n ) { TreeNode * node = q . front (); q . pop (); if ( node -> left ) { q . push ( node -> left ); } if ( node -> right ) { q . push ( node -> right ); } } } return ans ; } };

1# Definition for a binary tree node. # class TreeNode: # def __init__(self, val=0, left=None, right=None): # self.val = val # self.left = left # self.right = right class Solution : def rightSideView ( self , root : Optional [ TreeNode ]) -> List [ int ]: ans = [] if root is None : return ans q = deque ([ root ]) while q : ans . append ( q [ - 1 ]. val ) # add last node of previous level traversal results for _ in range ( len ( q )): node = q . popleft () if node . left : q . append ( node . left ) if node . right : q . append ( node . right ) return ans ############# # Definition for a binary tree node. # class TreeNode(object): # def __init__(self, x): # self.val = x # self.left = None # self.right = None from collections import deque class Solution ( object ): def rightSideView ( self , root ): """ :type root: TreeNode :rtype: List[int] """ def dfs ( root , h ): if root : if h == len ( ans ): ans . append ( root . val ) # pre-order, all the way to the right dfs ( root . right , h + 1 ) dfs ( root . left , h + 1 ) ans = [] dfs ( root , 0 ) return ans

Video walkthrough

Newsletter

One sharp idea, every week

System design and interview prep — short enough to finish.

No spam. Unsubscribe anytime.

Practice

Same difficulty — related problems to reinforce the pattern.

← Previous

Previous problem

Next problem