Approach - 1
Brute - iterative
TC-> O(N)
SC-> O(N)
1) We will use level order traversal to find the right view.
2) Basically right view will be last element of the each level if put in array
3) So our rightmost element will be when queue size==0
4) so insert the node data in ans array if size ==0
vector<int> printRightViewFirst(BinaryTreeNode<int>* root) {
vector<int> ans;
if(root==NULL) return ans;
queue<BinaryTreeNode<int>*> q;
q.push(root);
while(!q.empty()){
int size = q.size();
while(size--){
BinaryTreeNode<int>* front = q.front(); q.pop();
if(size==0) ans.push_back(front->data);
if(front->left) q.push(front->left);
if(front->right) q.push(front->right);
}
}
return ans;
}
Approach - 2
Recursively
TC-> O(N)
SC-> O(Auxilary)
1) Here we will use preorder traversal as in it preorder Root->left->right
2) Now we will use ulta preorder traversal means root->right->left
3) we will insert every level first element in ans array.
4) basically if level==ans.size() we will insert that root value
5) Now we will do the recursively ulta preorder traversal
void reversePreorder(BinaryTreeNode<int>* root,vector<int> &ans,int level){
if(root==NULL) return ;
if(level==ans.size()){ans.push_back(root->data);}
reversePreorder(root->right,ans,level+1);
reversePreorder(root->left,ans,level+1);
}
vector<int> printRightView(BinaryTreeNode<int>* root) {
vector<int> ans;
if(root==NULL) return ans;
reversePreorder(root,ans,0);
return ans;
}
