Java binary search trees
A binary search tree (BST) stores values so that, for every node, all values in its left subtree are smaller and all values in its right subtree are larger. Searching and inserting follow one path from the root, comparing at each step, so they take time proportional to the height of the tree.
Java
import java.util.*;
class Main {
static class Node {
int value;
Node left;
Node right;
Node(int value) {
this.value = value;
}
}
static Node insert(Node root, int value) {
if (root == null) {
return new Node(value);
}
if (value < root.value) {
root.left = insert(root.left, value);
} else if (value > root.value) {
root.right = insert(root.right, value);
}
return root;
}
static boolean contains(Node root, int value) {
while (root != null) {
if (value == root.value) {
return true;
}
root = value < root.value ? root.left : root.right;
}
return false;
}
static void inOrder(Node root, List<Integer> out) {
if (root == null) {
return;
}
inOrder(root.left, out);
out.add(root.value);
inOrder(root.right, out);
}
static int height(Node root) {
return root == null ? 0 : 1 + Math.max(height(root.left), height(root.right));
}
public static void main(String[] args) {
Node root = null;
for (int v : new int[] {50, 30, 70, 20, 40, 60, 80, 40}) {
root = insert(root, v);
}
List<Integer> sorted = new ArrayList<>();
inOrder(root, sorted);
System.out.println(sorted);
System.out.println(contains(root, 60) + " " + contains(root, 65));
System.out.println("height " + height(root));
Node chain = null;
for (int v = 1; v <= 7; v++) {
chain = insert(chain, v);
}
System.out.println("height of the chain " + height(chain));
}
}