Search nested lists for an Item

Question

Say I have an object of type T with a field with an ArrayList that holds objects of type T that I will call list. I also have another object of type T that I will call goal. I am trying to find goal. To do this, I want to first iterate through the list to see if goal is there. If it is, I want to return the original object. If it is not, then I want to go object by object through list and check each of these lists for goal (returning the object if found). I want to continue this search recursively until a match is found.

I cannot figure out how to accomplish this. The two options I could think of were while loops and recursion. However, I have to oscillate between levels as I check the various lists and I cannot figure out how to do that.

Another thought I had was that what I want to do is the same thing as a level-order transversal of a tree. However, I have only learned about binary trees so far and I don't know how or if I could convert it to a tree much less if it's possible to do a level order traversal without traversing the whole tree.

Below, see code that I have written so far. This will only check to see if the first list matches and does not go deeper which is what I need.

/**
     * Searches for the shortest path between start and end points in the graph.
     * @param start
     * @param end
     * @return a list of data, starting with start and ending with end, that gives the path through
     * the graph, or null if no such path is found.  
     */
    public List<T> shortestPath(T startLabel, T endLabel){
        List<T> list = new ArrayList<>();
        list.add(startLabel);
        while(true){
            List<T> successors = successorList(startLabel);
            if (containsMatch(successors, endLabel)) {
                findMatch(successors, endLabel);
            }
        }
    }

Does this scenario make sense? If so, any thoughts? Is it even possible? (I tried searching but all of my queries turned up nothing useful)

Thanks in advance for any help. Cheers!

Answer 1

T does sound like it represents a tree, but this is ONLY if for every T in its ArrayList, (and every T in each of their ArrayLists, etc.), all T's are unique. Otherwise, traversing it like a tree when it is not one could lead to infinite loops.

I don't understand what you mean by "if it's possible to do a level order traversal without traversing the whole tree". If your tree T has no sense of order, then you will have to traverse the whole tree because the goal T could be anywhere. That is precisely what you want to do, no?

Thinking of this problem as two mutually recursive functions might help conceptually. One function could be called SearchT, and the other could be called SearchArrayListT. SearchT checks if T is the "goal" T. If not, it calls SearchArrayListT on its field of ArrayList of T's.

If the ArrayList passed in is empty, SearchArrayListT produces "false" (i.e. however you represent the fact that the goal has not been found.) Otherwise, SearchArrayListT calls SearchT on every element of the ArrayList, checking after each one if "true" is returned (or however you represent the fact that the goal is found). This is actually a depth first search, but you should get the same result. You can see how one would do a breadth first search on the wikipedia page for them: https://en.wikipedia.org/wiki/Breadth-first_search

For your problem specifically, it looks like you're finding the path from the "root" T to the "goal" T, so during this mutual recursion, you'd wanna be passing the "path so far", and appending to that "path so far" along the recursion. More specifically, SearchT would append take in the pathSoFar, and then call SearchArrayListT with the pathSoFar appended with the "T" that SearchT also took in as an argument. Something like this:

SearchT(T t, List<T> pathSoFar) //append t to pathSoFar, check if 
//t is the goal; if it is not call SearchArrayListT(t.list, pathSoFar.add(t)); 

SearchArrayListT(ArrayList<T>, List<T> pathSoFar)

Answer 2

If you are trying to find an item in a graph recursively you can use depth first search.

During traversal you will need to mark the visited nodes so that you do not keep visiting them in a loop. You will only visit children of a node in case these have not yet been visited.

Here is a simple Java implementation using DFS which searches a tree recursively for a value in the tree and then captures the node if found.

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

public class TreeSearch<T> {

    private final Set<T> marked = new HashSet<>();

    private boolean found;

    private Node<T> foundNode;

    public TreeSearch(Node<T> node, T s) {
        dfs(node, s);
    }

    private void dfs(Node<T> node, T s) {
        if(node.value.equals(s)) {
            found = true;
            foundNode = node;
        }
        marked.add(node.value);
        if(node.children != null) {
            for (Node<T> child : node.children) {
                if (!marked.contains(child.value)) {
                    dfs(child, s);
                }
            }
        }
    }

    public boolean isFound() {
        return found;
    }

    public Node<T> getFoundNode() {
        return foundNode;
    }

    public static void main(String[] args) {
        Node<Integer> root = new Node<>(0);
        Node<Integer> n1 = new Node<>(1);
        Node<Integer> n2 = new Node<>(2);
        root.add(n1);
        root.add(n2);
        n2.add(n1);
        Node<Integer> n3 = new Node<>(3);
        n2.add(n3);

        TreeSearch<Integer> search = new TreeSearch<>(root, 3);
        assert search.isFound();
        System.out.println(search.isFound()); // Expects true
        System.out.println(search.getFoundNode());

        TreeSearch<Integer> searchFail = new TreeSearch<>(root, 4);
        assert !searchFail.isFound();
        System.out.println(searchFail.isFound()); // Expects false
    }

}

class Node<T> {

    T value;

    List<Node<T>> children;

    public Node(T value) {
        this.value = value;
    }

    public void add(Node<T> child) {
        if(children == null) {
            children = new ArrayList<>();
        }
        children.add(child);
    }

    @Override
    public String toString() {
        return "Node{" +
                "value=" + value +
                ", children=" + children +
                '}';
    }
}

If you run this class (it has a main method only for testing purposes) you will see this output:

true
Node{value=3, children=null}
false

This algorithm will not tell you the shortest path. It will only tell you, if a value is in the graph and in which node.

If you are trying to find the shortest path from a source node in a directed graph, better use Breadth-first search.