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

• Konrad Rudolph: Obvious question: why not do it recursively? This will make the code much simpler, and potentially more efficient. Furthermore, your code isn’t valid C++ and leaks memory. You should fix those two things.
• newbie: it is a interview question and it was specially mentioned to not use recursion. Can u please clarify what you mean by your code isn't valid c++ ??
• Konrad Rudolph: Well, my compiler has this to say: "foo.cpp:66:6: warning: ISO C++ forbids declaration of 'main' with no type [-pedantic]" Incidentally, I just noted that the code contains more bugs (flag=flag||0 does nothing, and using boolean operations to manipulate an integer flag, while working, isn’t meaningful anyway).
• newbie: my compiler does not show warning regarding implementation of strict ISO standards.That's why i tend to overlook them. But thanks for pointing that out.And i also need help with better implementation of the algorithm. It would be really great if you can help me with that.

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.

• newbie: Thank you,your answer was really helpful but could you tell me why is it wrong to use " using namespace std ". Does n't that save us the trouble of including std in front of cin and cout etc. ?
• Komi Golov: See, amongst others this question.
• Jamal: You should probably make the int main() part more apparent here, in case the OP hasn't already noticed it (and it's quite important).