c++functionrecursiontree-nodes

how to stop void function from stack overflow


Since void doesn't return anything, I don't know how to get a proper base case for a void function like the one I am trying to get.

struct TreeNode {
    char value;
    TreeNode *sibling;
    TreeNode *child;
};

void serialize(std::ostream &out, TreeNode *root) 
{
    // If the root is nullptr, print "None"
    if (root == nullptr)
        out << "None" << "\n";

    // Write out root's value
    out << root->value << "\n";

    // if there is no child
    //    write out "False"
    // else
    //    write out "True"
    //    recursively call serialize on that child
    if (root->child == nullptr)
        out << false << "\n";
    else
    {
        out << true << "\n";
        serialize(out, root->child);
    }
    // recursively call serialize on the sibling
    serialize(out, root->sibling);
}

Would it help if I rewrite serialize as a TreeNode type function instead, what would be my base case if I did that?

Note: this is one function from a project to create a tree-node data structure in c++.


Solution

  • In this code you are trying to call the serialize function recursively, but there is no termination condition specified. therefore as a result of which each time the recursive function-call the stack memory is occupied, eventually leading to stack overflow. Add the termination point like the return statement, it should work fine.

     if (root == nullptr)
            out << "None" << "\n";
        return;