Created
July 16, 2020 23:48
-
-
Save brianpursley/f9ee258cd970a5afc74b73bdbe1d45c8 to your computer and use it in GitHub Desktop.
Binary Search Tree DFS, BFS, and Search using Java
This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
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