Java Binary Search Tree Implementation

Chapter: Miscellaneous Last Updated: 21-03-2023 17:36:40 UTC

Program:

            /* ............... START ............... */
                public class Node {
    int data;
    Node left;
    Node right;

    public Node(int data) {
        this.data = data;
        this.left = null;
        this.right = null;
    }
}

public class BinarySearchTree {
    Node root;

    public BinarySearchTree() {
        root = null;
    }

    public void insert(int data) {
        root = insertRec(root, data);
    }

    public Node insertRec(Node root, int data) {
        if (root == null) {
            root = new Node(data);
            return root;
        }

        if (data < root.data) {
            root.left = insertRec(root.left, data);
        } else if (data > root.data) {
            root.right = insertRec(root.right, data);
        }

        return root;
    }

    public Node search(Node root, int data) {
        if (root == null || root.data == data) {
            return root;
        }

        if (data < root.data) {
            return search(root.left, data);
        }

        return search(root.right, data);
    }

    public void inorderTraversal() {
        inorderRec(root);
    }

    public void inorderRec(Node root) {
        if (root != null) {
            inorderRec(root.left);
            System.out.print(root.data + " ");
            inorderRec(root.right);
        }
    }

    public static void main(String[] args) {
        BinarySearchTree tree = new BinarySearchTree();
        tree.insert(50);
        tree.insert(30);
        tree.insert(20);
        tree.insert(40);
        tree.insert(70);
        tree.insert(60);
        tree.insert(80);

        System.out.println("Inorder traversal:");
        tree.inorderTraversal();

        System.out.println("\nSearching for 40:");
        Node result = tree.search(tree.root, 40);
        if (result != null) {
            System.out.println("Found " + result.data);
        } else {
            System.out.println("Not found");
        }
    }
}

                /* ............... END ............... */
        

Output

Inorder traversal:
20 30 40 50 60 70 80 
Searching for 40:
Found 40

Notes:

  • The program defines two classes - Node and BinarySearchTree. The Node class represents a node in the BST with an integer value, and two child nodes - left and right, which can also be null indicating the absence of a child node. The BinarySearchTree class defines the BST data structure with a root node, which can be null indicating an empty tree.
  • The BinarySearchTree class has several methods for operations on the BST. The insert(int data) method is used to insert a new node with the given data value into the BST by calling the recursive insertRec(Node root, int data) method. This method traverses the tree recursively, starting from the root node, to find the appropriate location to insert the new node based on its value.
  • The search(Node root, int data) method is used to search for a node with the given data value in the BST rooted at the specified root node. This method also traverses the tree recursively to find the node with the matching value.
  • Finally, the inorderTraversal() method is used to traverse the BST in order and print the values of the nodes. The inorderRec(Node root) method is a recursive helper method for the traversal.
  • In the main() method, a BinarySearchTree object is created, and some nodes are inserted into the BST using the insert() method. The inorderTraversal() method is then called to print the values of the nodes in the BST. Finally, the search() method is called to search for a node with a value of 40, and the result is printed.

Tags

# Java binary search tree library # Java Binary Search Tree Implementation # How to create a binary search tree

Similar Programs Chapter Last Updated
Swap Two Numbers Without Using Third Variable In Java Miscellaneous 02-06-2023
Java Program To Find The Average Of An Array Of Numbers Miscellaneous 02-06-2023
How Do You Find The Factorial Of A Number In Java Miscellaneous 02-06-2023
Java Program That Takes Two Numbers As Input And Prints Their Sum Miscellaneous 27-05-2023
How To Get The Length Of An Array In Java Miscellaneous 27-05-2023
Java Add Element To List Example Miscellaneous 19-05-2023
Java Program To Square All Items In List Miscellaneous 17-05-2023
Java Program To Merge Two Lists Miscellaneous 17-05-2023
How To Reverse A List In Java Miscellaneous 17-05-2023
Java Program To Find Unique Elements In An Array Miscellaneous 14-05-2023
Java Program To List All Elements In List Miscellaneous 30-04-2023
Java Program To Create XML File Miscellaneous 23-04-2023
Java Program To Run Something Every X Minutes Miscellaneous 22-04-2023
Java Program To Reverse A String Miscellaneous 22-04-2023
Java Program To Implement Method Overloading Miscellaneous 16-04-2023
Java Parse JSON String To Object Miscellaneous 24-03-2023
Java Program For Date And Time Miscellaneous 24-03-2023
Java Program To Merge Two PDF Files Miscellaneous 18-03-2023
How To Create A Git Repository | Git repository commands Miscellaneous 31-07-2021
Currency Formatter In Java | How To Format Currency In Java Miscellaneous 19-07-2021
Factory Design Pattern In Java Miscellaneous 11-05-2021
Data Types In Java Miscellaneous 09-06-2018

1