Binary Tree Level Order Traversal LeetCode

Question

Well this one question is from LeetCode. The question is to find the left most node of the last level of the tree. I tried it using a simple level order traversal by keeping one extra pointer for tracking the first element of each level(which will of course be the left most element).

While the code runs perfectly fine on my machine. It shows a different output in leetcode judge. Here is my code

int findBottomLeftValue(TreeNode* root) {
queue<TreeNode*>q;
q.push(root);
q.push(NULL);
TreeNode*first;

while(!q.empty())
{
   TreeNode*temp = q.front();
   q.pop();
   if(temp==NULL)
   {
     if(q.front()!=NULL)
       first = q.front();
     if(!q.empty())
        q.push(NULL);
    }
    else
    {
      if(temp->left)
      {
        q.push(temp->left);
      }
      if(temp->right)
      {
         q.push(temp->right);
      }
     }
    }
    return first->val;
}

For detailed analysis of the question visit https://leetcode.com/problems/find-bottom-left-tree-value/#/description

For the given test case [2,1,3] my code is giving the output 0 while the correct output is 1.

Any help is appreciated.

Unknown Unknown · Accepted Answer · 2017-05-12T14:39:51

At this point:

  if(q.front()!=NULL)

you do not know if there is anything in the queue. You should be testing wirth q.empty() before using q.front(). Your program therefore is exhibiting undefined behaviour.

Binary Tree Level Order Traversal LeetCode

1 Answers