4ms AC (in C++) level-order based solution. w/ explanation

  • 0

    Basically we're required to print the rightmost node in each level.
    I did a level-order traversal of the tree starting from the root maintaining a deque of TreeNode pointers corresponding to each node. We maintain a pushcount and popcount (counters for the pushes performed for each node in the deque) and intuitively for a level order the number of pushes into the deque due to the previous level's nodes is the number of nodes in the next level.
    If root == NULL there's obviously no solution. Otherwise start by pushing *root (popcount = 1 for the pushed root)

    Now we iteratively do the following until the deque becomes empty.

    popcount indicates the number pop_front() required to complete the current level.

    While popping a TreeNode from the deque we check the left and right pointers. If they are NOT NULL we push them to the deque. (increment pushcount )

    The last pop ie popcount == 1 would be the rightmost Node in that level. So do a push_back() to the returning vector. ( we can also do Binary Tree left side view by printing for the first pop instead of the last pop )

    class Solution {
        vector<int> rightSideView(TreeNode* root) {
            if(!root) {return{};}
            deque<TreeNode*> level;
            TreeNode* curr = root;
            int pushcount=0,popcount=1;
            vector<int> ret;
            while(!level.empty()){ // repeating till you've exhausted all the TreeNodes
                while(popcount !=0){ //repeating till you've exhausted the TreeNodes for the current level.
                    TreeNode* temp = level.front();
                    //if children != NULL push to deque
                    if(popcount == 1) ret.push_back(temp->val); // last pop has the rightmost node
                popcount = pushcount;
                pushcount = 0;
            return ret;

    popcount = pushcount and pushcount = 0 are done to repeat for the next level of TreeNodes.

Log in to reply

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