HiveBrain v1.2.0
Get Started
← Back to all entries
patterncppMinor

Tree-traversal without recursion

Submitted by: @import:stackexchange-codereview··
0
Viewed 0 times
codereviewstackcppc++stackoverflowalgorithmperformancetree
withoutrecursiontreetraversal

Problem

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
#include
#include
using namespace std;
struct node
{
int data;
vectorchildren;
};
int visited[100];
stack 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;
coutdatachildren.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;

Solution

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 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 path;
    std::set 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 data 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::coutchildren.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 path{root};
    std::set 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 data;
                }
                std::cout children.cbegin(), n->children.cend(), [&](node const& a) { return visited.find(&a) == visited.end(); }));
        }
    }
}


I am not sure which is more efficient.

Code Snippets

using namespace std;
struct node
{
    node(int d) : data(d) {}
    int data;
    boost::ptr_vector<node> children;
};
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);
}
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(); }));
        }
    }
}

Context

StackExchange Code Review Q#13150, answer score: 7

Revisions (0)

No revisions yet.