3

I want to print all the paths from the root to the leaf nodes in an N-ary tree in python. I have an idea to print it in binary tree but doing this in N-ary doesn't give me the correct result.

I'm poping and Visiting each node from the child node list here but not sure how to print the paths separately for each leaf node.

class createnode:
 def __init__(self,val):
   self.data=val
   self.child=[]

def traverse(root):
    global path
    if root.child:
     while(len(root.child)>0):
       x=root.child.pop(0)
       path.append(x.data)
       traverse(x)
    else:
      printarray(path)

def printarray(path):
  print(path)


root = createnode(10)
root.child.append(createnode(2))
root.child.append(createnode(4))

root.child[0].child.append(createnode(15))
root.child[0].child.append(createnode(20))
root.child[0].child.append(createnode(25))
root.child[0].child.append(createnode(30))

root.child[1].child.append(createnode(45))
root.child[1].child.append(createnode(50))
root.child[1].child.append(createnode(55))
root.child[1].child.append(createnode(60))
path=[]
total_val=30
traverse(root)

Expected output:

10, 2, 15

10, 2, 20

10, 2, 25

10, 2, 30

10, 4, 45

10, 4, 50

10, 4, 55

10, 4, 60

user7422128
  • 902
  • 4
  • 17
  • 41

2 Answers2

5

Try this:

def traverse(node, path = []):
    path.append(node.data)
    if len(node.child) == 0:
        print(path)
        path.pop()
    else:
        for child in node.child:
            traverse(child, path)
        path.pop()

Produces the following output with your example:

[10, 2, 15]
[10, 2, 20]
[10, 2, 25]
[10, 2, 30]
[10, 4, 45]
[10, 4, 50]
[10, 4, 55]
[10, 4, 60]
Valerio Preti
  • 183
  • 7
Jim Nilsson
  • 838
  • 4
  • 12
  • The last set of output [10, 2, 4, 45] should not have a 2 in it as 4 is the child of 10 not 2 – user7422128 Aug 18 '18 at 18:03
  • Oops, missed a line when I copy pasted from my editor. I've updated my answer. – Jim Nilsson Aug 18 '18 at 18:06
  • Appreciate your work. Can you please just put it in simple words though i got some clarity on the logic? @Jim – user7422128 Aug 18 '18 at 19:17
  • 1
    Sure. Every time a node is visited it is added to the current path. If the node has no children, the path is printed. Before the function returns, the last entry to the path is popped which will be the same entry as the one that was added when the function was entered. (The path.pop() can actually be moved to be after the if-else clause since both branches will perform that operation I see now.) – Jim Nilsson Aug 20 '18 at 06:51
0

If someone needs it in javascript:

findPaths(node, path, paths){
    let childrens = node.childrens;
    path.push(node);

    if(childrens.length == 0){
      paths.push(path.slice());

      path.pop();
    } else {
      for (let i = 0; i < children.length; i++) {
        findPaths(children, path, paths);
      }

      path.pop();
    }
}
Gabriel Sodre
  • 1
  • 1
  • Basically, is only the python code above transpiled to javascript. The function find all possible paths in a tree structure. – Gabriel Sodre May 21 '19 at 18:37