Creating a Binary Search Tree in Java

A Binary Search Tree (BST) is a data structure that stores data in a hierarchical form. It is composed of nodes, each of which stores a value and links to two other nodes. The left node stores a value smaller than the parent node, while the right node stores a value greater than the parent node.

Reason

Binary Search Trees are useful for quickly finding data stored in them. They can be used for sorting and searching data in an efficient manner. Furthermore, the data structure is easy to implement in Java and can be used in various applications.

Example code with output

public class BST {
    // root of the tree 
    Node root;

    // Node structure 
    class Node {
        int data;
        Node left, right;

        Node(int d) {
            data = d;
            left = right = null;
        }
    }

    // Inserts a new node 
    void insert(int data) {
        root = insertRec(root, data);
    }

    // A recursive function to insert a new data in BST 
    Node insertRec(Node root, int data) {

        // If the tree is empty, return a new node 
        if (root == null) {
            root = new Node(data);
            return root;
        }

        // Otherwise, recur down the tree 
        if (data < root.data)
            root.left = insertRec(root.left, data);
        else if (data > root.data)
            root.right = insertRec(root.right, data);

        // return the (unchanged) node pointer 
        return root;
    }

    // Driver Program 
    public static void main(String[] args) {
        BST tree = new BST();

        /* Let us create following BST 
              50 
           /      
          30      70 
         /      /   
        20   40  60   80 */
        tree.insert(50);
        tree.insert(30);
        tree.insert(20);
        tree.insert(40);
        tree.insert(70);
        tree.insert(60);
        tree.insert(80);

        System.out.println("Binary Search Tree created successfully!");
    }
}

Output: Binary Search Tree created successfully!