Binary Tree Right Side View medium

Problem Statement

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]

Steps

1. Level Order Traversal (BFS): We'll use Breadth-First Search (BFS) to traverse the tree level by level. BFS ensures we visit nodes from left to right within each level.

2. Rightmost Node per Level: For each level, we only care about the rightmost node's value. We'll track this using a queue and a variable to store the value of the rightmost node in the current level.

3. Result Vector: We'll store the rightmost node values of each level in a result vector.

Explanation

The algorithm employs a queue to perform a level-order traversal. In each level, we iterate through all nodes. The last node processed in a level is the rightmost node visible from the right side. We add this node's value to the result vector. The queue is updated with the children of nodes from the current level.

This approach guarantees that we only capture the rightmost node at each depth. We iterate through each level, processing nodes from left to right. The last node encountered in a level will be the rightmost, and its value is added to the output.

Code

#include <vector>
#include <queue>

using namespace std;

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> result;
        if (root == nullptr) return result;

        queue<TreeNode*> q;
        q.push(root);

        while (!q.empty()) {
            int levelSize = q.size();
            int rightmostValue = -1; // Initialize with an impossible value

            for (int i = 0; i < levelSize; ++i) {
                TreeNode* node = q.front();
                q.pop();
                rightmostValue = node->val; // Update rightmostValue for the current level

                if (node->left) q.push(node->left);
                if (node->right) q.push(node->right);
            }
            result.push_back(rightmostValue);
        }
        return result;
    }
};

Complexity

• Time Complexity: O(N), where N is the number of nodes in the tree. We visit each node exactly once.
• Space Complexity: O(W), where W is the maximum width of the tree. In the worst-case scenario (a complete binary tree), W can be equal to N, but in most cases, it will be less than N. The space is used by the queue to store nodes at each level.