mihirDepthFirstTraversal.java

package lmu.cmsi281.examples;

import java.util.ArrayList;

public class mihirDepthFirstSearch {
    public Boolean searchRecursive(BinaryTreeNodeString root, String element, ArrayList<String> path) {
        if (root == null) {
            return false;
        }
        path.add(root.getData());
        Boolean found = false;
        if (root.getData().equals(element)) {
            return true;
        }
        if (root.getLeft() != null) {
            found = found || // why do you need this?
            searchRecursive(root.getLeft(), element, path);
        }
        if (root.getRight() != null) {
            found = found  || // <- this too
            searchRecursive(root.getRight(), element, path);
        }
        return found;
    }

    public static void main(String[] args) {
        BinaryTreeNodeString root = new BinaryTreeNodeString("A");
        root.setLeft("B");
        root.setRight("C");
        root.getLeft().setLeft("D");
        root.getLeft().setRight("E");
        root.getRight().setLeft("F");
        root.getRight().setRight("G");
        root.getLeft().getLeft().setLeft("H");
        root.getLeft().getLeft().setRight("I");
        root.getLeft().getRight().setLeft("J");

        mihirDepthFirstSearch dfs = new mihirDepthFirstSearch();

        ArrayList<String> path = new ArrayList<String>();
        Boolean found;

        System.out.println("Using recursive search:");
        path.clear();
        found = dfs.searchRecursive(root, "H", path);
        System.out.println("Searching for H... " + "Found=" + found);
        System.out.println("path=" + path);

        path.clear();
        found = dfs.searchRecursive(root, "G", path);
        System.out.println("Searching for G... " + "Found=" + found);
        System.out.println("path=" + path);

        path.clear();
        found = dfs.searchRecursive(root, "Z", path);
        System.out.println("Searching for Z... " + "Found=" + found);
        System.out.println("path=" + path);
    }
}