Skip to content

Instantly share code, notes, and snippets.

@xnorcode
Last active July 30, 2018 18:23
Show Gist options
  • Save xnorcode/c9d05541176d84a9e8f1a65d8cbe994f to your computer and use it in GitHub Desktop.
Save xnorcode/c9d05541176d84a9e8f1a65d8cbe994f to your computer and use it in GitHub Desktop.
Check for path in a tree in a BFS method
...
// custom node class
public static class Node {
int id;
Node left;
Node right;
public Node(int id){
this.id = id;
}
}
public static boolean hasPathBFS(Node source, int destination){
// create a queue for nodes to be checked
Queue<Node> nextToCheck = new LinkedList<Node>();
// create set to temporarily store the id of the nodes we check
HashSet<Integer> visited = new HashSet<>();
// add source node into the queue for checking
nextToCheck.add(source);
// check nodes in queue
while(!nextToCheck.isEmpty()){
// get head node and remove from queue
Node node = nextToCheck.poll();
// head node null check
if(node == null) return false;
// check node
if(node.id == destination) return true;
// mark node as visited
if(!visited.contains(node.id)) visited.add(node.id);
// add children in the next to check queue
nextToCheck.add(node.left);
nextToCheck.add(node.right);
}
// if no path found
return false;
}
...
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment