199 Binary Tree Right Side View

Given a binary tree, imagine yourself standing on therightside of it, return the values of the nodes you can see ordered from top to bottom.

For example: Given the following binary tree,

   1            <---
 /   \
2     3         <---
 \     \
  5     4       <---

You should return[1, 3, 4].

The Idea: Run a level order traversal. Append null if you reach null as an indicator for the next level. It then follows that if the next element in the queue is null, we are on the right side of the tree.

Complexity: O(n) time and space

vector<int> rightSideView(TreeNode* root) {
    vector<int> right_side;
    if (!root) return right_side;

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

    while (!q.empty()) {
        TreeNode *front = q.front(); q.pop();
        if (front) {
            if (front->left) q.push(front->left);
            if (front->right) q.push(front->right);
            if (!q.front())
                right_side.push_back(front->val);
        }
        else if (!front && !q.empty()) {
            q.push(nullptr);
        }
    }

    return right_side;
}