What is binary trees ? it is tree data structure. It contains nodes. a top node is root. Each node contains left and right node. Left node is smaller than parent. Right node is bigger than parent.

Binary Search Tree (BST)

BST has an ability search really fast . Runtime is O(log n)
Node structure
private static class Node {
int key;
String value;
private Node left;
private Node right;
public Node(int key, String value) {
this.key = key;
this.value = value;
}
public Node min() {
if(left == null) {
return this;
}
return this.left;
}
}
Binary structure
public class BinarySearchTree {
private Node root;
public void insert(int key, String value) {}
public String find(int key) {}
public String delete(int key) {}
}
How to to insert ? Using the recursion to traversal down until see the null. Go left or right by checking the key. Left down if key less than current node key.
public void insert(int key, String value) {
this.insertItem(root, key, value);
}
private Node insertItem(Node node, int key, String value) {
Node newNode = new Node(key, value);
if(node == null) {
node = newNode;
return node;
}
if (key < node.key) {
node.left = insertItem(node.left, key, value);
} else {
node.right = insertItem(node.right, key, value);
}
return node;
}
How to find ?
public String find(int key) {
Node node = find(root, key);
return node == null ? null : node.value;
}
private Node find(Node node, int key) {
if(node == null || node.key == key) {
return node;
} else if(key < node.key) {
return find(node.left, key);
}
else if(key > node.key) {
return find(node.right, key);
}
return null;
}
How to delete ?
- Delete node has no child
- Delete node has one child
- Delete node has 2 children
public void delete(int key) {
root = delete(root, key);
}
private Node delete(Node node, int key) {
if(node == null) {
return null;
} else if(key <node.key) {
node.left = delete(node.left, key);
} else if(key > node.key) {
node.right = delete(node.right, key);
} else {
// Case 1: No child
if(node.left == null && node.right == null) {
node = null;
}
// Case 2 : One Child
else if ( node.left == null) {
node = node.right;
}
else if ( node.right == null) {
node = node.left;
}
// Case 3: Two children
else {
Node minRight = findMin(node.right);
node.key = minRight.key;
node.value = minRight.value;
//Now go delete the node we just duplicated
node.right = delete(node.right, node.key);
}
}
return node;
}
private Node findMin(Node node) {
return node.min();
}
Binary Tree Traversal :
- Depth First Traversal
- Inorder (Left, Root, Right)
- Preorder (Root, Left, Right)
- Postorder (Left, Right, Root)
- Breadth Traversal
Binary Search Tree Runtime : O (log n)
Binary Search Tree is Ordered
Binary Search Tree is recursive
Binary Search is super fast