Code Implementation

# 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

from collections import deque

class Solution:
    def rightSideView(self, root):
        if not root:
            return []
        result = []
        queue = deque([root])
        while queue:
            level_length = len(queue)
            for i in range(level_length):
                node = queue.popleft()
                if node.left:
                    queue.append(node.left)
                if node.right:
                    queue.append(node.right)
                if i == level_length - 1:
                    result.append(node.val)
        return result
      

// Definition for a binary tree node.
// struct TreeNode {
//     int val;
//     TreeNode *left;
//     TreeNode *right;
//     TreeNode(int x) : val(x), left(NULL), right(NULL) {}
// };

#include <vector>
#include <queue>

class Solution {
public:
    std::vector<int> rightSideView(TreeNode* root) {
        std::vector<int> result;
        if (!root) return result;
        std::queue<TreeNode*> q;
        q.push(root);
        while (!q.empty()) {
            int levelSize = q.size();
            for (int i = 0; i < levelSize; ++i) {
                TreeNode* node = q.front(); q.pop();
                if (node->left) q.push(node->left);
                if (node->right) q.push(node->right);
                if (i == levelSize - 1) result.push_back(node->val);
            }
        }
        return result;
    }
};
      

// Definition for a binary tree node.
// public class TreeNode {
//     int val;
//     TreeNode left;
//     TreeNode right;
//     TreeNode(int x) { val = x; }
// }

import java.util.*;

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

/**
 * 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 = function(root) {
    if (!root) return [];
    let result = [];
    let queue = [root];
    while (queue.length > 0) {
        let levelSize = queue.length;
        for (let i = 0; i < levelSize; i++) {
            let node = queue.shift();
            if (node.left) queue.push(node.left);
            if (node.right) queue.push(node.right);
            if (i === levelSize - 1) result.push(node.val);
        }
    }
    return result;
};
      

Problem Description

The "Binary Tree Right Side View" problem asks you to return the values of the nodes that are visible when you look at a binary tree from its right side. For each level of the tree, only the rightmost node is visible. Given the root of a binary tree (root), you must output a list of integers representing the values of these rightmost nodes, ordered from top to bottom.

• Each node contains a value (val), a left child (left), and a right child (right).
• The tree may be empty (in which case, return an empty list).
• There is a unique path from the root to each node (no cycles).

Thought Process

To solve this problem, we need to identify the rightmost node at each level of the tree. A brute-force approach might involve traversing every node and somehow keeping track of the maximum horizontal position, but that's unnecessarily complex.

Instead, we can use a level-order traversal (also known as Breadth-First Search, or BFS). By visiting nodes level by level, we can easily identify the last node at each level, which is the one visible from the right side.

Alternatively, a Depth-First Search (DFS) approach could be used, prioritizing right children first and keeping track of the first node visited at each depth. However, BFS is more intuitive for this problem because it naturally groups nodes by level.

The main insight is: At each level, the last node we visit is the rightmost node for that level.

Solution Approach

• Step 1: Check for empty tree. If the root is null, return an empty list.
• Step 2: Initialize a queue. Use a queue to perform BFS, starting with the root node.
• Step 3: Traverse level by level. For each level:
  • Determine the number of nodes at this level (queue size).
  • Iterate through all nodes at this level.
  • For each node, add its left and right children (if any) to the queue for the next level.
  • When processing the last node at the current level (i.e., the final iteration of the loop), record its value in the result list.
• Step 4: Continue until all levels are processed. Repeat step 3 until there are no more nodes in the queue.
• Step 5: Return the result. The result list now contains the rightmost node values for each level, from top to bottom.

This approach uses a queue because it allows us to efficiently process nodes level by level (FIFO order). At each level, by tracking the last node processed, we guarantee that we capture the rightmost node for that depth.

Example Walkthrough

Consider the following binary tree:

        1
       / \
      2   3
       \   \
        5   4
  

Let's trace the algorithm step by step:

1. Start with the root node (1) in the queue.
2. Level 1: Only node 1 is present. It's the rightmost node. Add 1 to the result.
3. Enqueue its children: 2 and 3.
4. Level 2: Nodes are 2 and 3. The last node is 3. Add 3 to the result.
5. Enqueue their children: 2 has right child 5; 3 has right child 4.
6. Level 3: Nodes are 5 and 4. The last node is 4. Add 4 to the result.
7. Neither 5 nor 4 have children. The queue is now empty.

The final output is [1, 3, 4], which are the nodes visible from the right side.

Time and Space Complexity

• Brute-force: A brute-force solution might traverse every path and check visibility, but this would be inefficient and could require O(N^2) time in the worst case for unbalanced trees.
• Optimized (BFS) Approach:
  • Time Complexity: O(N), where N is the number of nodes in the tree. Each node is visited exactly once.
  • Space Complexity: O(D), where D is the maximum number of nodes at any level (the tree's maximum width). In the worst case (a full binary tree), this is O(N/2) = O(N).

The BFS approach is both time and space efficient for this problem.

Summary

The "Binary Tree Right Side View" problem is elegantly solved using a breadth-first (level-order) traversal. By processing each level and recording the last node encountered, we efficiently capture the rightmost visible nodes. This approach leverages the natural structure of the tree and avoids unnecessary computation, resulting in a clear and optimal solution.