BST Breadth-First Search
123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354555657585960616263646566676869707172737475767778798081828384858687888990919293949596979899100101102103104105106107108109110111112113114115116117118119120121122123124125126127128
import java.util.ArrayList;
import java.util.Arrays;
import java.util.LinkedList;
import java.util.Queue;
class Main {
public static void main(String[] args) {
BinaryTree bt = new BinaryTree();
bt.add(6);
bt.add(4);
bt.add(8);
bt.add(3);
bt.add(5);
bt.add(7);
bt.add(9);
System.out.println(Arrays.toString(bt.traverseLevelOrder().stream().map(r -> r.value).toArray()));
bt.delete(7);
System.out.println(Arrays.toString(bt.traverseLevelOrder().stream().map(r -> r.value).toArray()));
}
}
class Node {
int value;
Node left;
Node right;
Node(int value) {
this.value = value;
right = null;
left = null;
}
}
class BinaryTree {
Node root;
public void add(int value) {
root = addRecursive(root, value);
}
private Node addRecursive(Node current, int value) {
if (current == null) {
return new Node(value);
}
if (value < current.value) {
current.left = addRecursive(current.left, value);
} else if (value > current.value) {
current.right = addRecursive(current.right, value);
} else {
// value already exists
return current;
}
return current;
}
public boolean containsNode(int value) {
return containsNodeRecursive(root, value);
}
//Binary search
private boolean containsNodeRecursive(Node current, int value) {
if (current == null) {
return false;
}
if (value == current.value) {
return true;
}
return value < current.value
? containsNodeRecursive(current.left, value)
: containsNodeRecursive(current.right, value);
}
public void delete(int value) {
root = deleteRecursive(root, value);
}
//Complicated part
private Node deleteRecursive(Node current, int value) {
if (current == null) {
return null;
}
if (value == current.value) {
// Node to delete found
if (current.left == null && current.right == null) {
return null;
}
if (current.right == null) {
return current.left;
}
if (current.left == null) {
return current.right;
}
int smallestValue = findSmallestValue(current.right);
current.value = smallestValue;
current.right = deleteRecursive(current.right, smallestValue);
return current;
}
if (value < current.value) {
current.left = deleteRecursive(current.left, value);
return current;
}
current.right = deleteRecursive(current.right, value);
return current;
}
private int findSmallestValue(Node root) {
return root.left == null ? root.value : findSmallestValue(root.left);
}
public ArrayList<Node> traverseLevelOrder() {
ArrayList<Node> res = new ArrayList<Node>();
Queue<Node> nodes = new LinkedList<>();
nodes.add(root);
while (!nodes.isEmpty()) {
Node node = nodes.remove();
res.add(node);
if (node.left != null) {
nodes.add(node.left);
}
if (node.right!= null) {
nodes.add(node.right);
}
}
return res;
}
}
Java
INFO