Print every leaf path of a tree without recursive

Question

How do I print every leaf path of a tree without using recursion.

It is a tree, NOT a binary tree

struct node {
    int data
    std::vector<node*> children;
}

Print all the path from root to leaf, i.e. the following is the tree

• r:is the root node
• d, m, n are r's children
• x,y,z are d's children
• there is no child for m
• o, p are n's children

-------------root
------d         m          n
---x  y  z              o  p

The result should be:

root-d-x
root-d-y
root-d-z
root-m
root-n-o
root-n-p

I tried to use non-recursive way but failed.

Answer 1

public static void printAllPathToLeafNonRecursive(Node root) {

    if (root == null) {
        return;
    }

    Queue<Object> q = new LinkedList<Object>();
    q.add(root);
    q.add(root.data + "");

    while(!q.isEmpty()){

        Node head = (Node) q.poll();
        String headPath = (String) q.poll();

        if(head.isLeaf()){
            System.out.println(headPath);
            continue;
        }

        if(head.left!=null){
            String leftStr =  headPath + "->" + head.left.data;
            q.add(head.left);
            q.add(leftStr);
        }

        if(head.right!=null){
            String rightStr =  headPath + "->" + head.right.data;
            q.add(head.right);
            q.add(rightStr);
        }
    }


}

Answer 2

Here's a Python solution based purely on pre-order iterative traversal using a stack. Prints both the paths and pathsums.

 class Stack(object): # just for reference
    def __init__(self):
        self.a = []

    def push(self, b):
        self.a.append(b)

    def peek(self):
        return self.a[-1]

    def pop(self):
        return self.a.pop()

    def isEmpty(self):
        return len(self.a) == 0

    def show(self):
        return self.a

 def paths(troot): # you should create your own Tree and supply the root
    current = troot
    s = Stack()
    s.push(current)
    s.push(str(current.key))
    s.push(current.key)

    while not s.isEmpty():
        pathsum = s.pop()
        path = s.pop()
        current = s.pop()

        if not current.left and not current.right:
            print 'path: %s, pathsum: %d' % (path, pathsum)

        if current.right:
            rightstr = path + "->" + str(current.right.key)
            rightpathsum = pathsum * 10 + current.right.key
            s.push(current.right)
            s.push(rightstr)
            s.push(rightpathsum)

        if current.left:
            leftstr = path + "->" + str(current.left.key)
            leftpathsum = pathsum * 10 + current.left.key
            s.push(current.left)
            s.push(leftstr)
            s.push(leftpathsum)

For example, for the following tree:

                          3                                                
                       /   \
                      /     \
                     /       \
                    /         \
                   /           \
                  /             \
                 /               \
                /                 \
              1                       7                        
           /   \                   /   \
          /     \                 /     \
         /       \               /       \
        /         \             /         \
        0           2           5           8            
     /   \       /   \       /   \       /   \
    /     \     /     \     /     \     /     \
   NUL   NUL   NUL   NUL     4     6   NUL     9      

The output would be:

    >>> paths()
    path: 3->1->0, pathsum: 310
    path: 3->1->2, pathsum: 312
    path: 3->7->5->4, pathsum: 3754
    path: 3->7->5->6, pathsum: 3756
    path: 3->7->8->9, pathsum: 3789