Leetcode problem - Binary Tree Right Side View

general
1

Problem Link: - LeetCode

Can anyone suggest a possible correction to my code ?
I am getting Time-Limit-Exceeded while running the code.

     /**
    * Definition for a binary tree node.
    * struct TreeNode {
    *     int val;
    *     TreeNode *left;
    *     TreeNode *right;
    *     TreeNode() : val(0), left(nullptr), right(nullptr) {}
    *     TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
    *     TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), 
    right(right) {}
 * };
 */
  
   class Solution {
   public:
   vector<int> rightSideView(TreeNode* root) 
   {
    vector<int> v;
    if(root==NULL)
        return v;
    queue<TreeNode*> q;
    q.push(root);
    
    while(!q.empty())
    {
        int n = q.size();
        for(int i=0;i<n;i++)
        {
            TreeNode *curr = q.front();
            q.pop();
            
            if(i!=n-1)
               continue;
            else
               v.push_back(curr->val);
                
            if(root->left!=NULL)
                q.push(root->left);
            if(root->right!=NULL)
                q.push(root->right);
            
        }
        
    }
   return v; 
}
};
3 
if(root->left!=NULL)
                q.push(root->left);
            if(root->right!=NULL)
                q.push(root->right);

This is wrong, you must check for curr->left and curr->right and then push them into your queue. Also you are continuing for i != (n-1) case which skips the nodes of non-rightmost tree nodes.

vector<int> rightSideView(TreeNode* root)

{
vector v;
if(root==NULL)
return v;
queue<TreeNode*> q;
q.push(root);

while(!q.empty())
{
    int n = q.size();
    for(int i=0;i<n;i++)
    {
        TreeNode *curr = q.front();
        q.pop();
        
       if(i == (n-1))
           v.push_back(curr->val);
            
        if(curr->left!=NULL)
            q.push(curr->left);
        if(curr->right!=NULL)
            q.push(curr->right);
        
    }
    
}

return v;
}

Here is your corrected code!!!

2 Likes
5

The logic you are trying to apply is basically to see all the nodes in a level order traversal and put the last node of every level.
But you have a given a condition if(i!=n-1) continue; due to this statement your traversal is getting terminated abruptly.
So the correction is just remove that condition and put if(i==n-1) v.push_back(curr->val);

After that when you are pushing nodes in the queue, you are pushing the root->left and root->right which will obviously put this loop in an infinite situation, you need to push curr->left and curr->right instead.

After Correction :

while(!q.empty())
{
    int n = q.size();
    for(int i=0;i<n;i++)
    {
        TreeNode *curr = q.front();
        q.pop();
        
        if(i==n-1)
             v.push_back(curr->val);

            
        if(curr->left!=NULL)
            q.push(curr->left);

        if(curr->right!=NULL)
            q.push(curr->right);
        
    }
    
}

Hope you understood :slight_smile:

1 Like
6

Thanks, pushing root->left and root->right inside the queue is a terrible mistake, and I hope I won’t repeat it again, Thanks a lot for your explanations :blush:

7

Thanks, I thought that we can avoid those nodes which are irrelevant to us in the queue by using the keyword “continue”. But I think, that proved to be a wrong choice in this problem. Thanks a lot for your explanations for the mistake I did in case of queue insertions :blush:

1 Like