How would you find the number of paths to this tree in Java?

user_9855703 0
Viewed 109

I am trying to find the number of paths to a tree represented this way:

1 4
2 4
3
4
-1

-1 represents the end and each number represents the next node. Each line is a node and their number starts with 0. So, in this particular instance, there are 3 paths: 0>1>2>3>4>-1, 0>4>-1, and 0>1>4>-1.

enter image description here

import java.io.*;
import java.util.*;

public class PathFinder {
    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);
        ArrayList<ArrayList<String>> wholeList = new ArrayList<ArrayList<String>>();
        while (scanner.hasNext()) {
            String input = scanner.nextLine();
            
            StringTokenizer st = new StringTokenizer(input, " ");

            ArrayList<String> temp = new ArrayList<String>();
            while(st.hasMoreTokens()) {
                temp.add(st.nextToken());
            }
            wholeList.add(temp);
        }

        return count;
    }
}
tree breadth-first-search depth-first-search search java
1 Answers

I suggest you change your arrays so that they contain integer numbers and not strings. Then you can use a recursive solution:

import java.io.*;
import java.util.*;

public class PathFinder {
    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);
        List<List<Integer>> wholeList = new ArrayList<>();
        while (scanner.hasNext()) {
            String input = scanner.nextLine();
            
            StringTokenizer st = new StringTokenizer(input, " ");

            List<Integer> temp = new ArrayList<>();
            while(st.hasMoreTokens()) {
                temp.add(Integer.valueOf(st.nextToken()));
            }
            wholeList.add(temp);
        }
        countRoutes(wholeList, 0);
        System.out.println(count);
    }
    
    private static int count = 0;

    private static void countRoutes(List<List<Integer>> tree, int nodeFrom) {
        for (Integer target : tree.get(nodeFrom)) {
            if (-1 == target) {
                count++;
            } else {
                countRoutes(tree, target);
            }
        }
    }
}

If you want to see the routes you can modify the method a bit:

private static void printRoutes(List<List<Integer>> tree, int nodeFrom, String route) {
    for (Integer target : tree.get(nodeFrom)) {
        if (-1 == target) {
            count++;
            System.out.println(route + "->-1");
        } else {
            printRoutes(tree, target, route + "->" + target);
        }
    }
}

and call it from the main program as

printRoutes(wholeList, 0, "0");

Update 03-Mar-2021

A more efficient way is to cache the number of paths leading to the end from a given node:

private static int countRoutes(List<List<Integer>> tree, 
                               int nodeFrom, 
                               int[] pathsNumber)
{
    if (nodeFrom == -1) {
        return 1;
    }
    if (pathsNumber[nodeFrom] >= 0) {
        return pathsNumber[nodeFrom];
    }

    int sum = 0;
    for (Integer target : tree.get(nodeFrom)) {
        sum += countRoutes(tree, target, pathsNumber);
    }
    pathsNumber[nodeFrom] = sum;
    return sum;
}

Then in the main method you initialize the array pathsNumber and call this method as following (-1 means that we have not calculated number of paths leading to the exit from this node yet):

int[] pathsNumber = new int[wholeList.size()];
Arrays.fill(pathsNumber, -1);
System.out.println(countRoutes(wholeList, 0, pathsNumber));
user_129521130
Related