CODEWITHSUNDEEP
c++binary-tree
devsaw
devsaw

Reputation: 1047

BST: void value not ignored as it ought to be

I was trying to implement a BST in C++.This is a specific member function to perform in order traversal and return a vector with the elements of the tree. Now the problem arises with the stack pop() function which I set to the current node.
void value not ignored as it ought to be

I understand that the empty stack will return a void value after the preceding pop() call.But then what's the solution to this, cause it's required in this traversal algorithm to retrieve the last node from the stack. 

vector <int> BSTree::in_order_traversal()
{

vector <int> list;
stack <Node *> depthStack;
Node * cur = root;

while ( !depthStack.empty() || cur != NULL ) {
                if (cur != NULL) {
                         depthStack.push(cur);
                         cur = cur->left;
                                                     }
                else                             {
                         cur = depthStack.pop(); // Heres the line 
                         list.push_back(cur->key);
                         cur = cur->right;
                                                      }

                                                                                                                                            }
return list;

}

Upvotes: 6

Views: 10580

Answers (2)

Sandeep Bhatt
Sandeep Bhatt

Reputation: 1

In C++ stack.pop() function doesn't return the value from the stack.

So ,first you store the values and then you pop it. In your case:

vector <int> BSTree::in_order_traversal()
{

vector <int> list;
stack <Node *> depthStack;
Node * cur = root;

while ( !depthStack.empty() || cur != NULL ) {
                if (cur != NULL) {
                         depthStack.push(cur);
                         cur = cur->left;
                                                     }
                else                             {
                         cur = depthStack.top();   //solution
                                 depthStack.pop();                             
                         list.push_back(cur->key);
                         cur = cur->right;
                                                      }

                                                                                                                                            }
return list;

}

Upvotes: 0

6502
6502

Reputation: 114539

In C++ the method

std::stack::pop()

doesn't return the value removed from the stack. The reason is that there's no way in general to write such a function correctly from an exception-safety point of view.

You need to store the value first and then remove it with pop... e.g.

Node *x = depthStack.top();
depthStack.pop();

Upvotes: 17

Related Questions