Skip to content

Instantly share code, notes, and snippets.

@brianpursley
Created July 16, 2020 23:48
Show Gist options
  • Star 0 You must be signed in to star a gist
  • Fork 0 You must be signed in to fork a gist
  • Save brianpursley/f9ee258cd970a5afc74b73bdbe1d45c8 to your computer and use it in GitHub Desktop.
Save brianpursley/f9ee258cd970a5afc74b73bdbe1d45c8 to your computer and use it in GitHub Desktop.
Binary Search Tree DFS, BFS, and Search using Java
package example;
import java.util.ArrayDeque;
import java.util.Arrays;
public class BstExample {
static class Node {
private int value;
private Node left;
private Node right;
public Node(int value, Node left, Node right) {
this.value = value;
this.left = left;
this.right = right;
}
}
static class BinarySearchTree {
private Node root;
public BinarySearchTree(int[] values) {
Arrays.sort(values);
this.root = sortedArrayToBst(values, 0, values.length - 1);
}
public Node sortedArrayToBst(int[] values, int start, int end) {
if (start > end) {
return null;
}
var mid = (start + end) / 2;
return new Node(values[mid],
sortedArrayToBst(values, start, mid - 1),
sortedArrayToBst(values, mid + 1, end)
);
}
}
static class Searcher {
public static Node find(Node node, int value) {
if (node == null) {
return null;
}
if (node.value == value) {
return node;
}
if (node.value > value) {
return find(node.left, value);
}
return find(node.right, value);
}
}
static class DepthFirstVisitor {
public static void visit(Node node) {
if (node == null) {
return;
}
visit(node.left);
System.out.println(node.value);
visit(node.right);
}
}
static class BreadthFirstVisitor {
public static void visit(Node node) {
if (node == null) {
return;
}
var q = new ArrayDeque<Node>();
q.add(node);
while (!q.isEmpty()) {
node = q.remove();
System.out.println(node.value);
if (node.left != null) {
q.add(node.left);
}
if (node.right != null) {
q.add(node.right);
}
}
}
}
public static void main(String[] args) {
var bst = new BinarySearchTree(new int[] {7, 1, 6, 5, 2, 3, 4});
for (var i = 1; i < 10; i++) {
if (Searcher.find(bst.root, i) != null) {
System.out.println("Searcher found " + i);
} else {
System.out.println("Searcher did not find " + i);
}
}
System.out.println();
System.out.println("Depth First Visitor:");
DepthFirstVisitor.visit(bst.root);
System.out.println();
System.out.println("Breadth First Visitor:");
BreadthFirstVisitor.visit(bst.root);
}
/*
Output:
Found 1
Found 2
Found 3
Found 4
Found 5
Found 6
Found 7
Did not find 8
Did not find 9
Depth First Visitor:
1
2
3
4
5
6
7
Breadth First Visitor:
4
2
6
1
3
5
7
*/
}
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment