Getting paths from root to leaves in a specific tree encoding

Question

I have a tree represented as a Set<Integer>[]

The following Set<Integer>[]:

[ { 1 }, { 2, 3 }, { 4 }, { 5, 6, 7 } ]

represents the following tree:

      1
     / \
    /   \
   /     \
  2       3
  |       |
  4       4
 /|\     /|\
5 6 7   5 6 7

So each level in the tree is encoded as a Set. All set of children at a particular level in the tree are the same. There can be more than one integers in the first set.

I want to get, from the Set<Integer>[], a list of all the paths from root to leaves:

[ [ 1, 2, 4, 5 ], [ 1, 2, 4, 6 ], [ 1, 2, 4, 7 ], [ 1, 3, 4, 5 ], [ 1, 3, 4, 6 ], [ 1, 3, 4, 7 ] ]

Answer 1

The Key for Searching in trees is usually implementing a good Ajacency function that gives the adjacent nodes for a specific node.

For this tree, adjacency function would want to find which level the node lies in, and then return the nodes in the next level as adjacents. It will look something like that:

  /**
   * This returns the adjacent nodes to an integer node in the tree
   * @param node
   * @return a set of adjacent nodes, and null otherwise
   */
  public Set<Integer> getAdjacentsToNode(Integer node) {

    for (int i = 0; i < tree.size(); i++) {
      Set<Integer> level = tree.get(i);
      if (level.contains(node) && i < tree.size() - 1) {
        return tree.get(i + 1);
      }
    }
    return null;
  }

Assuming that we already have the tree defined as a field in the class.

Before we run our search we would want to initalize setting the root appropriately and doing some prework to the paths. Therefore we do the following:

/**
 * initializes our search, sets the root and adds it to the path
 */
  public void initialize() {
    root = -1;
    for (Integer node : tree.get(0)) {
      root = node;
    }
    currentPath.add(root);
  }

Assuming that currentPath and root are already defined as fields.

Then, we run a DFS search on the tree appending each node to our current path as we traverse the tree, and adding that path to our set paths and reseting it when we reach a deadend (the leafs):

  /**
   * runs a DFS on the tree to retrieve all paths
   * @param tree
   */
  public void runDFS(Integer node) {
    if (getAdjacentsToNode(node) != null) {
      for (Integer adjNode : getAdjacentsToNode(node)) {
        currentPath.add(adjNode);
        runDFS(adjNode);
      }
      currentPath.remove(currentPath.size() -1);
    } else {
      paths.add(currentPath.toArray(new Integer[0]));
      currentPath.remove(currentPath.size() -1);
    }
  }

The whole class, therefore, looks like this:

import java.util.ArrayList;
import java.util.Arrays;
import java.util.HashSet;
import java.util.List;
import java.util.Set;

public class DFS {
  private List<Integer> currentPath = new ArrayList<Integer>();
  private List<Integer[]> paths = new ArrayList<Integer[]>();
  private ArrayList<Set<Integer>> tree;
  private Integer root;
  /**
   * constructor
   * @param tree
   */
  public DFS(ArrayList<Set<Integer>> tree) { 
    this.tree = tree;
  }

  public List<Integer[]> getPaths() {
    return paths;
  }
  public void setPaths(List<Integer[]> paths) {
    this.paths = paths;
  }
  public Integer getRoot() {
    return root;
  }
  public void setRoot(Integer root) {
    this.root = root;
  }

/**
 * initializes our search, sets the root and adds it to the path
 */
  public void initialize() {
    root = -1;
    for (Integer node : tree.get(0)) {
      root = node;
    }
    currentPath.add(root);
  }

  /**
   * This returns the adjacent nodes to an integer node in the tree
   * @param node
   * @return a set of adjacent nodes, and null otherwise
   */
  public Set<Integer> getAdjacentsToNode(Integer node) {

    for (int i = 0; i < tree.size(); i++) {
      Set<Integer> level = tree.get(i);
      if (level.contains(node) && i < tree.size() - 1) {
        return tree.get(i + 1);
      }
    }
    return null;
  }

  /**
   * runs a DFS on the tree to retrieve all paths
   * @param tree
   */
  public void runDFS(Integer node) {
    if (getAdjacentsToNode(node) != null) {
      for (Integer adjNode : getAdjacentsToNode(node)) {
        currentPath.add(adjNode);
        runDFS(adjNode);
      }
      currentPath.remove(currentPath.size() -1);
    } else {
      paths.add(currentPath.toArray(new Integer[0]));
      currentPath.remove(currentPath.size() -1);
    }
  }
}

To test it, we try this:

public static void main(String[] args) { 
    ArrayList<Set<Integer>> tree = new ArrayList<Set<Integer>>();
    Set<Integer> level1 = new HashSet<Integer>();
    level1.add(new Integer(1));

    Set<Integer> level2 = new HashSet<Integer>();
    level2.add(new Integer(2));
    level2.add(new Integer(3));

    Set<Integer> level3 = new HashSet<Integer>();
    level3.add(new Integer(4));

    Set<Integer> level4 = new HashSet<Integer>();
    level4.add(new Integer(5));
    level4.add(new Integer(6));
    level4.add(new Integer(7));

    tree.add(level1);
    tree.add(level2);
    tree.add(level3);
    tree.add(level4);

    DFS dfsSearch = new DFS(tree); 
    dfsSearch.initialize();
    dfsSearch.runDFS(dfsSearch.getRoot());

    for (Integer[] path : dfsSearch.getPaths()) { 
      System.out.println(Arrays.toString(path));
    }

and we get the following output:

[1, 2, 4, 5]
[1, 2, 4, 6]
[1, 2, 4, 7]
[1, 3, 4, 5]
[1, 3, 4, 6]
[1, 3, 4, 7]