A Cool way to do tree / graph traversal

As part of the latest skills review – I am going back over my coding and trying to get better. Being honest I have been pleasantly surprised, but embarrassed, by some of the places I have found I have room for improvement. It is worth it though – cause sometimes you catch gems like this.

When traversing trees, I tend to traverse them like they were graphs, and using queues. So for the problem of traverse a binary tree (not a BST), and return the largest value in each row I wrote the following code:

    vector largestValues(TreeNode* root) {
        vector maxrowval;
        
        if( root == NULL )
            return(maxrowval);
        
        queue > treesearch;
        treesearch.push(make_pair(root,0));
        
        while( !treesearch.empty()){
            TreeNode* curNode = treesearch.front().first;
            int curDepth = treesearch.front().second;
            treesearch.pop();
            
            if( maxrowval.size() <= curDepth ){
                maxrowval.push_back(curNode->val);
            }
            
            if( maxrowval[curDepth] < curNode->val ){
                maxrowval[curDepth] = curNode->val;
            }
            
            if( curNode->left != NULL ){
                treesearch.push(make_pair(curNode->left, curDepth+1));
            }
            
            if( curNode->right != NULL ){
                treesearch.push(make_pair(curNode->right, curDepth+1));
            }
        }
        
        return( maxrowval );
    }

What I just ran across was someone who wrote the following code for the same problem. He is using a list as opposed to a queue – but the logic of what we are doing is about the same. Only his double nested loop traversal of the list should be much faster. It avoids a lot of pushing and popping operations, and leaves the constructed search list intact. I am posting this here so I can come back and look at this later. This is the kind of thing I am going to want to stew on and see where else it might be a useful thing to have in the toolbox.

    vector largestValues(TreeNode* root) {
        vector result;
        list current;
        
        if (root != nullptr) {
            current.push_back(root);
        }
        
        while (current.size()) {
            int max_value = INT_MIN;
            int size = current.size();
            while (size) {
                TreeNode* node = current.front();
                max_value = max(max_value, node->val);
                current.pop_front();
                if (node->left != nullptr) {
                    current.push_back(node->left);
                }
                
                if (node->right != nullptr) {
                    current.push_back(node->right);
                }
                size--;
            }
            result.push_back(max_value);
        }
        
        return result;
    }