DEV Community

Karhik Suryadevara
Karhik Suryadevara

Posted on

3 2

Binary Search Tree implementation in java

Binary search tree(bst) key points

1) binary search tree is a nonlinear data structure
2) In a bst each node has at most 2 children
3) it takes logarithmic time (O(long)) to find an element or insert an element in a bst, for comparison, it takes O(n) i.e linear time to find an element in an array.
4) no duplicates are allowed in bst

code to implement bst in java

import java.util.ArrayList;
import java.util.List;

public class BinarySearchTree {
    public TreeNode root;

    BinarySearchTree(int rootValue) {
        root = new TreeNode(rootValue);
    }

    BinarySearchTree() {
        root = null;
    }

    public boolean insert(int value) {
        if (root == null) {
            root = new TreeNode(value);
            return true;
        } else {
            return insert(value, root);
        }
    }

//    ********************************* Breadth first search ***************************************

    public List<Integer> BreadthFirstSearch() {
        return BreadthFirstSearch(root);
    }

    public List<Integer> BreadthFirstSearch(TreeNode root) {
        ArrayList<Integer> bfs_list = new ArrayList<Integer>();
        ArrayList<TreeNode> q = new ArrayList<TreeNode>();
        q.add(root);
        while (q.size() > 0) {
            TreeNode currNode = q.remove(q.size() - 1);
            bfs_list.add(currNode.value);
            if (currNode.left != null) {
                q.add(0, currNode.left);
            }
            if (currNode.right != null) {
                q.add(0, currNode.right);
            }
        }
        return bfs_list;
    }
    //    ******************************************************************************************

    //  ******************** Depth first search inorder,preorder,postorder **********************

    public List<Integer> depthFirstSearch_InOrder() {
        ArrayList<Integer> dps_lst = new ArrayList<Integer>();
        return traverseInOrder(root, dps_lst);
    }

    public List<Integer> traverseInOrder(TreeNode root, List<Integer> dps_lst) {
        if (root.left != null) traverseInOrder(root.left, dps_lst);
        dps_lst.add(root.value);
        if (root.right != null) traverseInOrder(root.right, dps_lst);
        return dps_lst;
    }

    public List<Integer> depthFirstSearch_PreOrder() {
        ArrayList<Integer> dps_lst = new ArrayList<Integer>();
        return traversePreOrder(root, dps_lst);
    }

    public List<Integer> traversePreOrder(TreeNode root, List<Integer> dps_lst) {
        dps_lst.add(root.value);
        if (root.left != null) traversePreOrder(root.left, dps_lst);
        if (root.right != null) traversePreOrder(root.right, dps_lst);
        return dps_lst;
    }

    public List<Integer> depthFirstSearch_PostOrder() {
        ArrayList<Integer> dps_lst = new ArrayList<Integer>();
        return traversePostOrder(root, dps_lst);
    }

    public List<Integer> traversePostOrder(TreeNode root, List<Integer> dps_lst) {
        if (root.left != null) traversePostOrder(root.left, dps_lst);
        if (root.right != null) traversePostOrder(root.right, dps_lst);
        dps_lst.add(root.value);
        return dps_lst;
    }

    //    ******************************************************************************************

    //    *************************** insert a node **********************************

    public boolean insert(int value, TreeNode root) {
        if (root.value == value) return false;
        if (value < root.value) {
            if (root.left != null) return insert(value, root.left);
            else {
                root.left = new TreeNode(value);
                return true;
            }
        } else {
            if (root.right != null) return insert(value, root.right);
            else {
                root.right = new TreeNode(value);
                return true;
            }
        }
    }

    //    ******************************************************************************************



    //    ******************* delete a node from tree **********************

    public List<TreeNode> findNodeAlsoItsParent(int value) {
        TreeNode parent = null;
        return findNodeAndItsParent(parent, root, value);
    }

    public List<TreeNode> findNodeAndItsParent(TreeNode parent, TreeNode root, int value) {
        ArrayList<TreeNode> lst = new ArrayList<TreeNode>();
        if (value == root.value) {
            lst.add(parent);
            lst.add(root);
            return lst;
        }
        if (value < root.value) {
            if (root.left != null) {
                return findNodeAndItsParent(root, root.left, value);
            } else {
                return null;
            }
        } else {
            if (root.right != null) {
                return findNodeAndItsParent(root, root.right, value);
            } else {
                return null;
            }
        }
    }

    public void delete(int value) {
        List<TreeNode> lst = findNodeAlsoItsParent(value);
        TreeNode nodeToBeDeleted = lst.get(1);
        TreeNode parentNode = lst.get(0);
        List<Integer> nodes = new ArrayList<Integer>();
        List<Integer> effectedNodes = traversePreOrder(nodeToBeDeleted, nodes);
        effectedNodes.remove(effectedNodes.indexOf(value));

        if (parentNode == null) {
//            if the node to be deleted is root
            root = null;
        } else {
            if (parentNode.left.value == value) parentNode.left = null;
            else parentNode.right = null;
        }
//        rearrange the binary tree from the effected nodes array
        for (int i : effectedNodes) {
            this.insert(i);
        }
    }
    //    ******************************************************************************************


    //  ***************************** TreeNode ****************************************
    public static class TreeNode {
        public int value;
        public TreeNode left;
        public TreeNode right;

        TreeNode(int value) {
            this.value = value;
            this.left = this.right = null;
        }
    }
//    *********************************************************************************************
}
Enter fullscreen mode Exit fullscreen mode

driver code

BinarySearchTree myBST = new BinarySearchTree();
        myBST.insert(100);
        myBST.insert(21);
        myBST.insert(111);
        myBST.insert(20);
        myBST.insert(50);
        myBST.insert(101);
        myBST.insert(112);

//                 100
//             /        \
//            21        111
//           / \        /  \
//         20   50     101  112

        System.out.println("Breadth First Search " + myBST.BreadthFirstSearch());
        System.out.println("Depth First Search In Order " + myBST.depthFirstSearch_InOrder().toString());
        System.out.println("Depth First Search Pre Order " + myBST.depthFirstSearch_PreOrder().toString());
        System.out.println("Depth First Search Post Order " + myBST.depthFirstSearch_PostOrder().toString());
        myBST.delete(100);
        System.out.println("Depth First Search In Order " + myBST.depthFirstSearch_InOrder().toString());

Enter fullscreen mode Exit fullscreen mode

output


Breadth First Search [100, 21, 111, 20, 50, 101, 112]
Depth First Search In Order [20, 21, 50, 100, 101, 111, 112]
Depth First Search Pre Order [100, 21, 20, 50, 111, 101, 112]
Depth First Search Post Order [20, 50, 21, 101, 112, 111, 100]
after deleting root node i.e 100
Depth First Search In Order [20, 21, 50, 101, 111, 112]
Enter fullscreen mode Exit fullscreen mode

Postmark Image

Speedy emails, satisfied customers

Are delayed transactional emails costing you user satisfaction? Postmark delivers your emails almost instantly, keeping your customers happy and connected.

Sign up

Top comments (0)

Image of Docusign

🛠️ Bring your solution into Docusign. Reach over 1.6M customers.

Docusign is now extensible. Overcome challenges with disconnected products and inaccessible data by bringing your solutions into Docusign and publishing to 1.6M customers in the App Center.

Learn more