# Weird Time Limit Exceeded Error (Using Morris Traversal in c++)

• My program ends in the OJ but it still reports Time Limit Exceeded. I have explicitly printed program end using cout.

I don't expect anyone to understand my code but see why I am getting Time Limit Exceeded when program is ending.

Here is my code:

``````/**
* Definition for a binary tree node.
* struct TreeNode {
*     int val;
*     TreeNode *left;
*     TreeNode *right;
*     TreeNode(int x) : val(x), left(NULL), right(NULL) {}
* };
*/
TreeNode* firstNode,*secondNode;
int flag;
void checkNode(TreeNode* &node1, TreeNode* &node2 ){
if(node2==NULL)
return;
if(node1->val>node2->val && flag==0){
//  cout<<"firstnode"<<endl;
firstNode = node1;
secondNode = node2;
flag=1;
//   if(firstNode==NULL)
//        cout<<"FirstNode is null in the function"<<endl;
}
else if(node1->val>node2->val && flag==1){
int temp = node2->val;
node2->val = firstNode->val;
firstNode->val = temp;
flag=2;
// cout<<"Nodes Swapped"<<endl;
}
}

class Solution {
public:

void recoverTree(TreeNode* root) {
flag=0;
TreeNode* current=root,*node1=NULL,*node2=NULL,*temp;
while(current){
//   cout<<"current:"<<current->val<<endl;
if(current->left){
temp = current->left;
while(temp->right!=NULL && temp->right!=current){
temp=temp->right;
}
if(temp->right==NULL){
temp->right=current;
current=current->left;
}
else{
temp->right=NULL;
if(node1==NULL)
node1=current;
else if(node2==NULL)
node2=current;
else{
node1=node2;
node2=current;
}
//             cout<<"Before checking 1:"<<endl;
checkNode(node1,node2);
//              cout<<"flag:"<<flag<<endl;
if(flag==2){

current=NULL;

}
else
current=current->right;
//    if(current==NULL)
//       cout<<"yes"<<endl;
//   if(firstNode==NULL)
//                  cout<<"FirstNode is null after returning"<<endl;
}

}
else {
if(node1==NULL)
node1=current;
else if(node2==NULL)
node2=current;
else{
node1=node2;
node2=current;
}

//         cout<<"Before checking 2:"<<endl;
checkNode(node1,node2);
//          cout<<"blahflag:"<<flag<<endl;
if(flag==2)
current=NULL;
else
current=current->right;
}
}
//   cout<<"Swapping end"<<endl;
if(flag==1){

//   if(firstNode==NULL)
//       cout<<"firstNode is Null";

//  if(secondNode==NULL)
//      cout<<"SecondNode is Null";

int temp = firstNode->val;
firstNode->val = secondNode->val;
secondNode->val = temp;
}
cout<<"Program Ends"<<endl;
}
};``````

• Morris modifies the tree structure, maybe you didn't manage to restore the structure properly and introduced a circle, which, when checking the result or printing the expected/actualy ends up in an infinite loop.

I can prove this by the following extremely simple malicious code run on any input:

``````void recoverTree(TreeNode* root) {
if (root) {
root->left = root;
root->right = root;
}
}``````

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