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] 
Top comments (0)