CODEWITHSUNDEEP
c++recursionwhile-loopstackbinary-search-tree
Rahul
Rahul

Reputation: 47

while loop executing infinitely without any recursive call even after execution flow reaches end of function containing while

below is a function i am using for inorder traversal of a binary search tree . Everything works well till the loop while(!st.empty()) gets terminated but after that the execution flow again goes to while(!st.empty()) hence loop turns into an infinite loop

structure of node

class bst{ 
private:
    bst *lLink;
    int info;
    bst *rLink;

friend void inorder(bst &);
 };
void inorder(bst &);

calling part

string c;
cout<<"\na, b or c ?";
cin>>c;

 if(c == "a")
 {
  inorder(nodeVec[0]);  //nodeVec is vector containing all nodes (objects) of tree with first element as root
 }

 //......

function

void inorder(bst &item)
{
stack<bst> st;
st.push(item);


while((st.top()).getLeftChild()!=NULL)
{
    st.push(*((st.top()).getLeftChild()));
}

while(!st.empty())
{
    if(st.top().getInfo()==item.getInfo()) //true if traversal is done with all
                                           //left subtree of root and only oneitem remained in stack i.e. only root remained
    {                                     
        cout<<st.top().getInfo()<<endl;

        if(st.top().getRightChild()!=NULL)
            inorder(*(item.getRightChild()));

        else
            st.pop();
    }

    else{
    cout<<st.top().getInfo()<<endl;
    if(st.top().getRightChild()!=NULL)
    {
        bst curr=*(st.top().getRightChild());
        st.pop();
        st.push(curr);
    }
    else{
        st.pop();
    }
    }
}
 cout<<st.empty();  //for testing, this prints 1
} //execution goes here and then again at while(!st.empty())

suppose the tree is like this:

      69
     /  \
    43  89
   /   /
  24  73
 /
14
 \
  21

it gives output

14
21
24
43
69
73
89
69   //loop starts again
73
89
69
73
89
...

Upvotes: 1

Views: 166

Answers (2)

Phillip Kinkade
Phillip Kinkade

Reputation: 1432

You should be removing the element from the stack when it's printed out.

You're leaving it on the stack in the first block of the if() that checks that the left side of the tree has been completed.

if(st.top().getRightChild()!=NULL)
    inorder(*(item.getRightChild()));

// else  // <--- don't use else here.. Always pop
    st.pop();

Upvotes: 3

andre
andre

Reputation: 7249

This seems way more complicated than it needs to be, Here is a untested version of what I think would work better.

struct bst{ 
    int info;
    bst *right;
    bst *left;
};

void inorder(bst & item) {
    std::stack<bst*> st;
    bst* current = &item;
    while(current || !st.empty()) {
        if(current) {
            st.push(current);
            current = current->left;
        } else {
            current = st.top();
            st.pop();
            std::cout << current->info << std::endl;
            current = current->right;
        }
    }
}

Upvotes: 0

Related Questions