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;
        }
    }
//    *********************************************************************************************
}

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());

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]