Traversing a binary tree using a vector return type

user_10193687 0
Viewed 148

I am trying to traverse a templated AVLtree with a key value pair and return a vector of all the values.

When using a cout statement, I can tell that the function is correctly traversing the tree and it will return all values in the tree. However, when I try to add this to a vector and use it in another part of my program, only the root node has been stored.


    vector<s> treeTraversal(){
         return treeTraversal(root);
    }

    vector<s> treeTraversal(AVLNode<t, s> *node ){
        vector<s> temp;

        if(node != nullptr){
            treeTraversal(node -> left);
            treeTraversal(node -> right);
            temp.push_back(node -> vectorToBe);
        }

        return temp;
    }

I am intending to store all the returned values in a vector so I can access them in a later part of my program

binary-search-tree nodes vector c++
2 Answers
treeTraversal(node -> left);

This recursively calls the function, this is one of the two recursive calls. Your treeTraversal() function returns a vector. However, here, its return values is thrown away and not stored anywhere.

return temp;

This is the vector that your function returns. However, as we've seen, it does not include anything that was returned from any recursive calls, because those returned values are thrown away and get ignored.

There are two usual ways to fix this:

  1. Do not ignore the returned vector from both recursive calls. Store them, then append their contents to temp.

  2. Instead of returning the std::vector make it an additional parameter to the recursive call. Each recursive call simply appends its value to the passed-in vector (and forwards it to any subsequent recursive calls). The caller of your recursive function will be responsible for instantiating an initially-empty vector, and passing it in.

user_39433120

I'd try something like this. You'll avoid creating a ton of vector<s>s in the stack.

vector<s> treeTraversal(){
     vector<s> result;
     treeTraversal(root, result);
     return result;
}

void treeTraversal(AVLNode<t, s> *node, vector<s>& visited ){
    if(node != nullptr){
        treeTraversal(node -> left, visited);
        treeTraversal(node -> right, visited);
        visited.push_back(node->vectorToBe);
    }
}
user_1357690
Related