https://leetcode.com/problems/binary-tree-right-side-view/description/?envType=study-plan-v2&envId=top-interview-150

Approach 1: BFS: Two Queues

Algorithm

• Initiate the list of the right side view rightside.
• Initiate two queues: one for the current level, and one for the next. Add root into nextLevel queue.
• While nextLevel queue is not empty:
  • Initiate the current level: currLevel = nextLevel, and empty the next level nextLevel.
  • While the current level queue is not empty:
    • Pop out a node from the current level queue.
    • Add first left and then right child node into nextLevel queue.
  • Now currLevel is empty, and the node we have in hands is the last one, and makes a part of the right side view. Add it into rightside.
• Return rightside.

/**
 * 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) {
        if (root == nullptr) return vector<int>();

        deque<TreeNode*> nextLevel{root};
        deque<TreeNode*> currLevel;
        vector<int> rightside;

        TreeNode* node = nullptr;
        while (!nextLevel.empty()){
            currLevel = nextLevel;
            nextLevel.clear();

            while (!currLevel.empty()){
                node = currLevel.front();
                currLevel.pop_front();

                if (node->left != nullptr) nextLevel.push_back(node->left);
                if (node->right != nullptr) nextLevel.push_back(node->right);
            }
            rightside.push_back(node->val);
        }
        return rightside;
    }
};

Complexity Analysis

• Time complexity: $O(N)$ since one has to visit each node.
• Space complexity: $O(D)$ to keep the queues, where $D$ is a tree diameter. Let's use the last level to estimate the queue size. This level could contain up to $N/2$ tree nodes in the case of complete binary tree.

Approach 2: BFS: One Queue + Sentinel

Algorithm

• Initiate the list of the right side view rightside.
• Initiate the queue by adding a root. Add null sentinel to mark the end of the first level.
• Initiate the current node as root.
• While the queue is not empty:
  • Save the previous node prev = curr and pop the current node from the queue curr = queue.poll().
  • While the current node is not null:
    • Add first left and then right child node into the queue.
    • Update both previous and current nodes: prev = curr, curr = queue.poll().
  • Now the current node is null, i.e. we reached the end of the current level. Hence the previous node is the rightmost one and makes a part of the right side view. Add it into rightside.
  • If the queue is not empty, push the null node as a sentinel, to mark the end of the next level.
• Return rightside.

/**
 * 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) {
        if (root == NULL) return vector<int>();

        queue<TreeNode*> queue;
        queue.push(root);
        queue.push(NULL);
        TreeNode *prev, *curr = root;
        vector<int> rightside;

        while (!queue.empty()){
            prev = curr;
            curr = queue.front();
            queue.pop();

            while (curr != NULL){
                // add child nodes in the queue
                if(curr->left != NULL){
                    queue.push(curr->left);
                }
                if(curr->right != NULL){
                    queue.push(curr->right);
                }
                prev = curr;
                curr = queue.front();
                queue.pop();
            }

            // the current level is finished
            // and prev is the rightmost element
            rightside.push_back(prev->val);

            // add a sentinel to mark the end
            // of the next level
            if (!queue.empty()) queue.push(NULL);
        }
        return rightside;
    }
};

Complexity Analysis