Tree-traversal without recursion

Question

I wrote the following code for printing all the paths to the leaf nodes in a tree (NOT a binary tree ) without using recursion. I have used a stack and performed dfs on the tree. Whenever I reach a leaf node I pop all the elements in the stack right till the root so that the function starts over again from the root and prints a path to another leaf.

The tree that I have assumed in the program is as follows

                              0
                      1            2       3
              4   5      6              7     8

Explanation:

• 1, 2 and 3 are children of 0;
• 4, 5, 6 are children of 1;
• 7 and 8 are children of 3.

My code

//print paths in a tree without recursion
#include<iostream>
#include<vector>
#include<stack>
using namespace std;
struct node                         
{
       int data;
       vector<node*>children;
};
int visited[100];
stack <node*> st;
int count=0;
int n;      
void printpath(node * root)                               //dfs starts here
{
     st.push(root);
     while(visited[0]==0)
     {
         node* v=st.top();
         if(visited[v->data]!=0)                 // leaf nodes or nodes whose all children 
            st.pop();                            // are visited are only popped from the stack
         if(visited[v->data])
            continue;
         cout<<v->data<<" ";
         int flag=0;
         for(int i=0;i<v->children.size();i++)      /*check if any of the children have not been visited*/
         {
                 if(visited[v->children[i]->data]==0)
                 {
                      flag=flag||1;
                      st.push(v->children[i]);
                 }
                 else
                       flag=flag||0;
         }

         /*if this is the leaf node then mark it visited and
         along with other intermediate nodes whose all the   
         children have been visited.this is continued till we
         reach root which has the value 0 in its data*/

         if(flag==0)
         {                                      
                 visited[v->data]=1;                       
                  while(v->data!=0)                         
                  {
                     v=st.top();
                     int flag=0;
                     for(int i=0;i<v->children.size();i++)
                     {
                        if(visited[v->children[i]->data]==0)
                          flag=flag||1;
                       else
                         flag=flag||0;
                     }
                        if(flag==0 && v->children.size()!=0)
                          visited[v->data]=1;
                        if(v->data!=0)
                          st.pop();
                  }
                  cout<<endl;
         }
     }
}
main()
{
   n=8;
   for(int i=0;i<9;i++)
       visited[i]=0;
   node*root = new node();                         //tree construction
   root->data=0;
   node* d = new node();
   d->data=1;
   node* m = new node();
   m->data=2;
   node* n = new node();
   n->data=3;
   root->children.push_back(d);
   root->children.push_back(m);
   root->children.push_back(n);
   node* x = new node();
   x->data=4;
   node* y = new node();
   y->data=5;
   node* z = new node();
   z->data=6;
   d->children.push_back(x);
   d->children.push_back(y);
   d->children.push_back(z);
   node* o = new node();
   o->data=7;
   node* p = new node();
   p->data=8;
   n->children.push_back(o);
   n->children.push_back(p);
   printpath(root);
}

My algorithm seems really inefficient. Can anyone suggest some ways to improve it?

The output is:

0 3 8 
0 3 7 
0 2 
0 1 6 
0 1 5 
0 1 4

Answer 1

In order that things appear in the code:

using namespace std;

This is unnecessary and generally bad practice. I would ask about it if I saw it in an interview question, although it is not harmful in this case.

struct node
{
    node(int d) : data(d) {}
    int data;
    boost::ptr_vector<node> children;
};

Indentation is generally done in powers of two, and should in any case be consistent. I'm switching to four-space indent everywhere, as you don't seem to be following any style.

This is also a great chance to use pointer containers. Each node owns all of its children, so use something that will enforce that. (In some cases, an std::vector of std::shared_ptrs would make more sense.)

You do not need any of the globals you've defined, and are definitely bad practice. You should also strive to be more const-correct.

void printpath(node const* root)
{
    std::stack<node const*> path;
    std::set<node const*> visited;
    path.push(root);
    while (visited.find(root) != visited.end())
    {
        node const* v = path.top();
        if (visited.find(v) != visited.end())
        {
            path.pop();
            continue;
        }
        std::cout << v->data << " ";
        bool has_unvisited_child = false; // Use bools for booleans.
        // See standard comments on iterators vs indices and preincrement
        // vs postincrement.
        for (auto it = v->children.cbegin(); it != v->children.cend(); ++it)
        {
            if (visited.find(&*it) != visited.end())
            {
                 has_unvisited_child = true;
                 st.push(&*it);
            }
        }

        // Don't rely on the root node having value 0 in its data.
        // You were given a pointer to it, use that.  Your algorithm
        // should not depend on the data stored in the tree.

        // Avoids some nesting.
        if (!has_unvisited_child)
            continue;

        visited.insert(v);                       
        while(v != root)                         
        {
            v = st.top();
            // Avoid shadowing.
            bool unvisited_child = 0;
            // Splitting this off into a function may be meaningful,
            // or using some standard algorithm such as std::any_of
            for (auto it = v->children.cbegin(); it != v->children.cend(); ++it)
                unvisited_child |= visited.find(&*it) != visited.end();
            if (!unvisited_child && !v->children.empty())
                visited.insert(v);
            if (v != root)
                st.pop();
        }
        std::cout<<endl;
    }
}

// main must return int
int main()
{
    node* root = new node(0);
    node* d = new node(1);
    node* m = new node(2);
    node* n = new node(3);
    root->children.push_back(d);
    root->children.push_back(m);
    root->children.push_back(n);
    node* x = new node(4);
    node* y = new node(5);
    node* z = new node(6);
    d->children.push_back(x);
    d->children.push_back(y);
    d->children.push_back(z);
    node* o = new node(7);
    node* p = new node(8);
    n->children.push_back(o);
    n->children.push_back(p);
    printpath(root);
}

Now for the performance part: My advice on that end is to not bother with the stack of next nodes and just keep track of the path:

void print_path(node const* root)
{
    std::vector<node const*> path{root};
    std::set<node const*> visited;
    while (!path.empty())
    {
        node const* n = path.back();
        if (std::all_of(n->children.cbegin(), n->children.cend(), [&](node const& a) { return visited.find(&a) != visited.end(); }))
        {
            if (n->children.empty()) {
                for (auto it = path.cbegin(); it != path.cend(); ++it)
                {
                    if (it != path.cbegin())
                        std::cout << ", ";
                    std::cout << (*it)->data;
                }
                std::cout << '\n';
            }
            visited.insert(n);
            path.pop_back();
        } else {
            path.push_back(&*std::find_if(n->children.cbegin(), n->children.cend(), [&](node const& a) { return visited.find(&a) == visited.end(); }));
        }
    }
}

I am not sure which is more efficient.