# 9ms C++ BFS, O(n) time, concise with explanation

• 9ms C++ iterative, concise code with explanation

Using a queue mQ to perform level order traversal. In the beginning of a level traversal, the last element is pushed into result array ret. The core idea is similar with Binary Tree Level Order Traversal

O(n) time, O(logn) space

``````class Solution {
public:
vector<int> rightSideView(TreeNode *root) {
queue<TreeNode*>mQ;
vector<int> ret;
if(!root)return ret;
mQ.push(root);
while(!mQ.empty()){
ret.push_back(mQ.back()->val);
for(int i=mQ.size();i>0;i--){
TreeNode *tn=mQ.front();
mQ.pop();
if(tn->left)mQ.push(tn->left);
if(tn->right)mQ.push(tn->right);
}
}
return ret;
}
};
``````

• space is O(logn), because it stores around one-level nodes.

• You are right, the space is O(logn) rather than O(n). I will change it. Thanks for pointing that out.

• Nope, the space is O(n) for the worst case of balanced tree. In that case, the last level would store half the number of total nodes.

• ``````vector<int> rightSideView(TreeNode* root) {
vector<int> out;
if (root == nullptr)
return out;
queue<TreeNode*> que;
que.push(root);
queue<TreeNode*>::size_type end = que.size();
while (!que.empty())
{
out.push_back(que.back()->val);
while (end--)
{
TreeNode *pop = que.front();
que.pop();
if (pop->left != nullptr)
que.push(pop->left);
if (pop->right != nullptr)
que.push(pop->right);
}
end = que.size();
}
return out;
}``````

• This post is deleted!

• @bo28 Not exactly.the worst space complex is O(n),since the number of leaf nodes of a perfect binary tree is n/2+1.

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.