I am trying to print all the paths from root to leaf in a tree, but having some issues collecting the path items.

Consider the following graph:

In my case though, the result is as follows:

10 -> 8 -> 3 -> 
10 -> 8 -> 3 -> 5 -> 
10 -> 8 -> 3 -> 5 -> 2 -> 2 -> 

So every path has the values from the previous nodes. This is how I am doing it:

class TreeNode(val n: Int, val children: MutableList<TreeNode> = mutableListOf())

fun main() {
    val root = TreeNode(10)
    val eight = TreeNode(8)
    val three = TreeNode(3)
    val five = TreeNode(5)
    val two = TreeNode(2)
    val twotwo = TreeNode(2)

    root.children.add(eight)
    root.children.add(two)
    eight.children.add(three)
    eight.children.add(five)
    two.children.add(twotwo)

    printTree(root, mutableListOf(), 0)
}

fun printTree(root: TreeNode, list: MutableList<Int>, index: Int) {
    list.add(root.n)

    if (root.children.isEmpty()) {
        list.forEach {
            print("$it -> ")
        }
        println()
    } else {
        root.children.forEach {
            printTree(it, list, index   1)
        }
    }
}

I understand that the issue stems from the fact that I am storing the items in the same list MutableList<Int> which is shared with every recursive call. Any ideas how can I adjust the implementation in order to produce the expected result?

CodePudding user response：

You need to remove the node before exiting the recursive method (as suggested in the comment). Implementation:

fun printTree(root: TreeNode, list: MutableList<TreeNode>) {
    list.add(root)
    root.children.forEach {
        printTree(it, list)
    }
    if (root.children.isEmpty())
        println(list.joinToString(" -> ") { it.n.toString() })
    list.removeLast()
}

Try it yourself

CodePudding user response：

This java code is what you need!

public class BinaryTreePrintAllPaths {
 
    public static class TreeNode
    {
        int data;
        TreeNode left;
        TreeNode right;
        TreeNode(int data)
        {
            this.data=data;
        }
    }
 
    // Prints all paths to leaf
    public static void printAllPathsToLeaf(TreeNode node, int[] path, int len) {
        if ( node == null )
            return;
 
        // storing data in array
        path[len] = node.data;
        len  ;
 
        if(node.left == null && node.right == null) {
            // leaf node is reached
            printArray(path,len);
            return;
        }
 
        printAllPathsToLeaf(node.left, path, len);
        printAllPathsToLeaf(node.right, path, len);
    }
 
    public static void main(String[] args)
    {
        // Creating a binary tree
        TreeNode rootNode=createBinaryTree();
        System.out.println("Printing all paths from root to leaf :");
        printAllPathsToLeaf(rootNode,new int[1000],0);
    }
 
    public static void  printArray(int[] path,int len)
    {
        for (int i = 0; i < len; i  ) {
            System.out.print(" " path[i]);
        }
        System.out.println();
    }
    
    
    public static TreeNode createBinaryTree()
    {
 
        // you can implement add method more elegant,I just did in this way to answer quickly
        
        TreeNode rootNode =new TreeNode(10);
        TreeNode node8=new TreeNode(8);
        TreeNode node3=new TreeNode(3);
        TreeNode node5=new TreeNode(5);
        TreeNode node2=new TreeNode(2);
        TreeNode node2_2=new TreeNode(2);
 
        rootNode.left=node8;
        rootNode.right=node2;
 
        node8.left=node3;
        node8.right=node5;
 
        node2.left=node2_2;
       
        return rootNode;
    }
}

CodePudding user response：

data class Node(
  val value: Int,
  val children: List<Node>? = null
)

val tree =
  Node(
    10, listOf(
      Node(
        8, listOf(
          Node(3), Node(5)
        )
      ),
      Node(
        2, listOf(
          Node(2)
        )
      )
    )
  )

// Create a list of lists, each list containing the nodes of a path
fun getAllPaths(node: Node): List<List<Node>> {
  return if (node.children.isNullOrEmpty()) {
    listOf(listOf(node))
  } else {
    node.children.flatMap { child -> getAllPaths(child) }.map { nodes -> listOf(node)   nodes }
  }
}

val paths = getAllPaths(tree)

// Print the values
paths.forEach { path -> println(path.joinToString(" -> ") { node -> node.value.toString() }) }
// 10 -> 8 -> 3
// 10 -> 8 -> 5
// 10 -> 2 -> 2

// Or alternatively extract the values from the nodes
val values = paths.map { nodes -> nodes.map { node -> node.value } }
values.forEach(::println)
// [10, 8, 3]
// [10, 8, 5]
// [10, 2, 2]