199. Binary Tree Right Side View

Description

Given the root of a binary tree, the task is to return the values of the nodes you can see ordered from top to bottom when looking at the tree from the right side.

Intuition

The right side view of a binary tree can be obtained by performing a level-order traversal (BFS) of the tree and capturing the last node's value at each level. Since we are interested in the rightmost nodes, traversing each level and noting the last node will provide the right side view.

Approach

1. Initialization: Start by initializing an empty result list and a queue for BFS.
2. BFS Traversal: Use a queue to perform BFS on the tree: - For each level, determine the number of nodes at that level. - Traverse all nodes at the current level, adding their children to the queue for the next level. - Keep track of the last node's value at each level and add it to the result list.
3. Return Result: After traversing all levels, the result list will contain the values of the rightmost nodes.

Complexity

Time Complexity:

O(n), where n is the number of nodes in the tree. Each node is processed once.

Space Complexity:

O(n), due to the space required to store the nodes in the queue.

Code

C++

class Solution {
public:
    vector rightSideView(TreeNode* root) {
        vector result;
        if (!root) return result;

        queue queue;
        queue.push(root);
        while (!queue.empty()) {
            int n = queue.size();
            vector values;
            for (int i = 0; i < n; ++i) {
                TreeNode* node = queue.front();
                queue.pop();
                if (node->left) queue.push(node->left);
                if (node->right) queue.push(node->right);
                values.push_back(node->val);
            }
            result.push_back(values.back());
        }
        return result;
    }
};

Python

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

Java

class Solution {
    public List rightSideView(TreeNode root) {
        List result = new ArrayList<>();
        if (root == null) return result;

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

JavaScript

var rightSideView = function (root) 
{

    if (!root) return [];
    let result = [];
    let queue = [];
    queue.push(root)
    while (queue.length) {
        let values = []
        let n = queue.length;
        for (let i = 0; i < n; i++) {
            let node = queue.shift();
            if (root) {
                if (node.left) queue.push(node.left);
                if (node.right) queue.push(node.right);
                values.push(node.val);
            }
        }
        console.log(values)
        result.push(values.pop());

    }
    return result;
};