Skip to content

Instantly share code, notes, and snippets.

@vnprc
Created October 13, 2016 02:56
Show Gist options
  • Save vnprc/313a72769f244795d62f4353aac37e41 to your computer and use it in GitHub Desktop.
Save vnprc/313a72769f244795d62f4353aac37e41 to your computer and use it in GitHub Desktop.
Two search algorithms for a tree, three implementations
import java.util.ArrayList;
import java.util.HashSet;
import java.util.LinkedList;
import java.util.List;
import java.util.Queue;
import java.util.Set;
import java.util.Stack;
public class Tree {
public List<Node> depthFirstSearchIterative(Node root) {
List<Node> results = new ArrayList<>();
Stack<Node> stack = new Stack<Node>();
Set<Node> visited = new HashSet<>();
stack.add(root);
while(!stack.isEmpty()) {
Node node = stack.pop();
if (!visited.contains(node)) {
visited.add(node);
stack.push(node);
for (Node child : node.getChildren()) {
stack.push(child);
}
} else {
results.add(node);
}
}
return results;
}
public List<Node> depthFirstSearchRecursive(Node root) {
List<Node> results = new ArrayList<>();
for (Node child : root.getChildren()) {
results.addAll(depthFirstSearchRecursive(child));
}
results.add(root);
return results;
}
public List<Node> breadthFirstSearch(Node root) {
List<Node> results = new ArrayList<>();
Queue<Node> queue = new LinkedList<Node>();
queue.add(root);
while(!queue.isEmpty()) {
Node node = queue.remove();
results.add(node);
queue.addAll(node.getChildren());
}
return results;
}
public static class Node {
private Object value;
private List<Node> children = new ArrayList<>();
public Node(Object value) {
this.value = value;
}
public void addChild(Node child) {
children.add(child);
}
public List<Node> getChildren() {
return children;
}
@Override
public String toString() {
return value.toString();
}
}
public static void main(String[] args) {
Tree tree = new Tree();
Node root = new Node("home");
Node documents = new Node("documents");
root.addChild(documents);
documents.addChild(new Node("tax_return_2015.pdf"));
documents.addChild(new Node("sales_receipt.pdf"));
documents.addChild(new Node("christmas_list.txt"));
Node pictures = new Node("pictures");
root.addChild(pictures);
Node kids = new Node("kids");
pictures.addChild(kids);
kids.addChild(new Node("baby.jpg"));
kids.addChild(new Node("vacation.jpg"));
pictures.addChild(new Node("silly.gif"));
// -> home
// -> pictures
// -> silly.gif
// -> kids
// -> baby.jpg
// -> vacation.jpg
// -> documents
// -> tax_return_2015.pdf
// -> sales_receipt.pdf
// -> christmas_list.txt
System.out.println("DFS iterative : " + tree.depthFirstSearchIterative(root));
System.out.println("DFS recursive : " + tree.depthFirstSearchRecursive(root));
System.out.println("BFS iterative : " + tree.breadthFirstSearch(root));
}
}
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment