Get a site

Create a Binary Search Tree (BST) from scratch

Today we will see how to create and implement a Binary Search Tree (BST) from scratch in Java.

I think that if you’re here it means that you know what’s a BST and so it’s useless to write another time all the theory of this Data Structure. Let start, remember that we need three files in order to create it.

Below you’ll find the complete and running code!

Main.java:

public class Main {

	public static void main(String[] args) {
		
		Tree t = new Tree();
		t.root = new Node();
		t.root.key = 5;
		
		Node a = new Node();
		a.key = 10;
		
		Node b = new Node();
		b.key = 2;
		
		Node c = new Node();
		c.key = 15;
		
		Node d = new Node();
		d.key = 7;
		

		t.insert(a);
		t.insert(b);
		t.insert(c);
		t.insert(d);
		
		t.inorderTreeWalk(t.root);
		
		System.out.println("Minimum node key: " + t.minimum().key);
		System.out.println("Maximum node key: " + t.maximum().key);
		
		System.out.println("Node with k = 15: " + t.search(15));
	}
}

Tree.java:

public class Tree {
	
	Node root;
	
	public void insert(Node z) {
		
		Node y = null;
		Node x = root;
		
		while(x != null) {
			
			y = x;
			
			if(z.key < x.key)
				x = x.left;
			else x = x.right;
		}		
			z.p = y;
			
			if(y == null)
				root = z;
			else if(z.key < y.key)
				y.left = z;
			else y.right = z;
	}
	
	public void inorderTreeWalk(Node root) {
		
		if(root != null) {
			inorderTreeWalk(root.left);
		
			System.out.println(root.key);
			
			inorderTreeWalk(root.right);
		}
	}
	
	public Node search(int key) {
		
		Node p = root;
		
		while(p != null && p.key != key) {
			if(key < p.key) 
				p = p.left;
			else p = p.right;
		}
		
		return p;
	}

	public Node minimum() {
		
		Node x = root;
		
		while(x.left != null) {
			x = x.left;
		}
		
		return x;
	}
	
	public Node maximum() {
		Node x = root;
		
		while(x.right != null) {
			x = x.right;
		}
		
		return x;
	}
}

Node.java:

public class Node {
	
	int key;
	Node p, left, right;

}

Probably I will write another article about the inorderTreeWalk() method to explain better how it works.

See ya 🙂