STL stack: Does calling stack.pop() invalidate stack.top() object?

[ElusiveTau]

This is from a Leetcode binary tree traversal exercise.

/**
 * 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> preorderTraversal(TreeNode* root) {
        if (!root) return vector<int>{};
        
        vector<int> visited;        
        stack<TreeNode*> stk; // stk: Stores nodes to be visited; top node is the next node to visit
        stk.push(root); // Initialize the stack with root node
        
        while (!stk.empty()) {
            auto node = stk.top();
            visited.push_back(node->val); // "Visit" the node
            stk.pop();
            
            // If children nodes exists, mark them for visitation 
            if (node->right) stk.push(node->right);
            if (node->left) stk.push(node->left); // Left child must be top element for preorder traversal. 
        }
        return visited;
    }
};

This code I've written is "accepted" (the function terminates with the expected output value) but I'm curious why calling stk.pop() didn't invalidate node (making subsequent use of node e.g., node->right on lines 27,28 invalid).

I think this question applies for other STL containers as well wherever the container's API allows you delete a container object.

Does stack.top() return a copy of the top-most container element?

[Peter87]

This

auto node = stk.top();

means the same as

TreeNode* node = stk.top();

[Peter87]

stk.top() does not return a copy, it returns a reference, but you immediately use the reference to create a copy before calling stk.pop() so that's not a problem.

If you instead had written

auto& node = stk.top();

which means the same as

TreeNode*& node = stk.top();

then it would have been a problem as you explained.

[ElusiveTau]

Peter87 wrote:

If you instead had written

auto& node = stk.top(); 
... then it would have been a problem as you explained.

I see. [1] says that stack.pop() calls the destructor for the element removed. Because the stack is one of pointer-to-TreeNode, the TreeNode(s) being pointed to still exists outside of this call, right? That is, only the pointers themselves are destroyed but not the TreeNodes being pointed to?

[1] https://www.cplusplus.com/reference/stack/stack/pop/

[keskiverto]

That is, only the pointers themselves are destroyed but not the TreeNodes being pointed to?

Exactly. Objects in stack are pointers. Objects (pointers) are destructed.

That is no different from:

int answer = 42;

{ // inner scope
  int* quiz = &answer;
} // inner scope ends 

At the end of inner scope the quiz goes out of scope and is destroyed. That has no effect on the answer.

A pointer is a simple type. It does not have a destructor that would deallocate the pointed to memory.
If it had, the example above would have fatal error, because answer cannot be dynamically allocated.

(Some) smart pointers manage memory that they do point to. Those class objects do have destructor that does deallocate.

[ElusiveTau]

keskiverto wrote:

Objects (pointers) are destructed

Understood. Had to check for myself:

// Example program
#include <iostream>
#include <string>
#include <vector>
#include <stack>

using std::vector;
using std::stack;
using std::cout;

//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) {}
    ~TreeNode() {
        cout << "TreeNode.dtor[val=" << val << "] called!\n";
    }
};

struct Tree {
    vector<TreeNode*> tree;

    // treeVals should be a valid array-representation of a binary tree
    Tree(const vector<int> treeVals) {
        if (treeVals.empty()) return;

        for (auto val : treeVals) tree.push_back(new TreeNode(val));

        // Set up the tree structure
        for (unsigned int i = 1; i < treeVals.size(); ++i) {
            if (i % 2 == 1) {
                tree[(i - 1) / 2]->left = tree[i];
            }
            else {
                tree[(i - 1) / 2]->right = tree[i];
            }
        }
    }
    ~Tree() {
        for (auto tn : tree) delete tn;
    }
};

class Solution {
public:
    static vector<int> preorderTraversal(TreeNode* root) {
        if (!root) return vector<int>{};

        vector<int> visited;
        stack<TreeNode*> stk; // stk: Stores nodes to be visited; top node is the next node to visit
        stk.push(root); // Initialize the stack with root node

        while (!stk.empty()) {
            auto node = stk.top();
            visited.push_back(node->val); // "Visit" the node
            stk.pop();

            // If children nodes exists, mark them for visitation 
            if (node->right) stk.push(node->right);
            if (node->left) stk.push(node->left); // Left child must be top element for preorder traversal. 
        }
        return visited;
    }
};


int main()
{
    // Picture of tree can be found here: https://en.wikipedia.org/wiki/Heap_(data_structure)
    Tree t1(vector<int>{100, 19, 36, 17, 3, 25, 1, 2, 7});

    for (auto val : Solution::preorderTraversal(t1.tree[0])) cout << val << ",";
    cout << "\n Exiting ...\n";
    return 0;
}

Output

100,19,17,2,7,3,36,25,1,
Exiting ...
TreeNode.dtor[val=100] called!
TreeNode.dtor[val=19] called!
TreeNode.dtor[val=36] called!
TreeNode.dtor[val=17] called!
TreeNode.dtor[val=3] called!
TreeNode.dtor[val=25] called!
TreeNode.dtor[val=1] called!
TreeNode.dtor[val=2] called!
TreeNode.dtor[val=7] called!

If TreeNode(s) were destroyed when pointers were destroyed, we would have seen the TreeNode dtor's output when preorderTraversal() was called.

Thanks, folks.

[keskiverto]

Had to check for myself

Awesome! You figured out a way to test a claim. That is a valuable skill.