Problem 27 - Binary Tree Right Side View

Explore our archive for previous posts.

Question

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]

Example 2:

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

Example 3:

Input: root = []
Output: []

Constraints:

• The number of nodes in the tree is in the range [0, 100].

• -100 <= Node.val <= 100

Approach

The solution aims to construct the right-side view of a binary tree, which means capturing the nodes that are visible when looking at the tree from the right side.

To achieve this, the solution uses a level-order traversal (BFS) approach. It performs a breadth-first search, processing the nodes level by level, starting from the root.

During the traversal, it keeps track of the rightmost node at each level. By iterating through the nodes at each level and adding the last node encountered (rightmost node) to the result list, it constructs the right-side view of the tree.

The algorithm utilizes a queue to store the nodes to be processed. It starts with the root node and then continues to process the child nodes level by level. At each level, it checks if the current node is the last node in that level, and if so, it adds its value to the result list.

By processing the nodes level by level and tracking the rightmost nodes, the solution effectively captures the right-side view of the binary tree.

Solution

Solve it here

class Solution {
    public List<Integer> rightSideView(TreeNode root) {
        List<Integer> result = new ArrayList<>();
        if (root == null) {
            return result;
        }
        
        Queue<TreeNode> queue = new LinkedList<>();
        queue.offer(root);
        
        while (!queue.isEmpty()) {
            int size = queue.size();
            
            for (int i = 0; i < size; i++) {
                TreeNode node = queue.poll();
                
                // Add the rightmost node at each level to the result
                if (i == size - 1) {
                    result.add(node.val);
                }
                
                if (node.left != null) {
                    queue.offer(node.left);
                }
                
                if (node.right != null) {
                    queue.offer(node.right);
                }
            }
        }
        
        return result;
    }
}

Time and space complexity

Time Complexity: The time complexity of the solution is O(n), where 'n' represents the number of nodes in the binary tree. The algorithm traverses each node in the tree once, performing constant-time operations at each step.

Space Complexity: The space complexity is O(m), where 'm' represents the maximum number of nodes at any level in the binary tree. In the worst case, the queue can store all the nodes at the maximum level, which can be roughly half the total number of nodes in a balanced binary tree. Therefore, the space complexity is proportional to the maximum width of the binary tree.

Explore more?

Missed a previous edition? Catch up on the insightful content you might have missed by visiting our archive here. Thank you for being a valued reader of our newsletter. We appreciate your continued support!