Approach 1: BFS a.k.a. Level Order Traversal
Straightforward approach where you perform a level order traversal and push the rightmost node in the level to the answer.
vector<int> rightSideView(TreeNode* root) {
queue<TreeNode*> q;
vector<int> v;
if (root == NULL)
return v;
int currLevel = 0;
unordered_map<TreeNode*, int> level;
TreeNode* top;
q.push(root);
level[root] = 0;
while (!q.empty()) {
top = q.front();
q.pop();
if (q.empty() || level[q.front()] != currLevel) { // rightmost node found!
v.push_back(top->val);
currLevel++;
}
if (top->left) {
level[top->left] = level[top]+1;
q.push(top->left);
}
if (top->right) {
level[top->right] = level[top]+1;
q.push(top->right);
}
}
return v;
}
Approach 2: DFS or modified preorder traversal
We can modify preorder traversal by going from root->right->left instead of root->left->right. This will lead us to the rightmost node of each level before traversing any other node in that level. See the code below and note how we identify when we have to push the node to the resulting array (i.e., how we identify that we are at the rightmost node). We leverage the fact that for each level we visit the rightmost node before visiting any other node.
vector<int> rightSideView(TreeNode* root) {
vector<int> res;
helper(root, res, 0);
return res;
}
void helper (TreeNode* node, vector<int>& res, int level) {
if (node==NULL) return;
if (level==res.size()) res.push_back(node->val);
helper(node->right, res, level+1);
helper(node->left, res, level+1);
}