Binary search tree in java

• Find
• Insert

Search()

Algorithm:

• If node to be found is equal to root, then search is successful
• If node to be found is smaller than root , then traverse left subtree.
• If node to be found is greater than root, then traverse right subtree
• Repeat above steps recursively until you find the node.

Algorithm:

• Make root node as current node
• If node to be inserted < root
  • If it has left child then traverse left
  • If it do not have left child, insert node here
• If node to be inserted > root
  • If it have right child, traverse right
  • If it do not have right child, insert node here.

Complete java program:

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 100 101 102

package org.arpit.java2blog.binarysearchtree;   public class BinarySearchTreeMain { public static class TreeNode { int data; TreeNode left; TreeNode right; TreeNode(int data) { this.data=data; } }     public static boolean search(TreeNode root,TreeNode nodeToBeSearched) { if(root==null) return false; if(root.data== nodeToBeSearched.data) { return true; } boolean result=false;   if(root.data > nodeToBeSearched.data) result=search(root.left,nodeToBeSearched); else if(root.data < nodeToBeSearched.data) result= search(root.right,nodeToBeSearched);   return result; }   public static TreeNode insert(TreeNode root,TreeNode nodeToBeInserted) { if(root==null) { root=nodeToBeInserted; return root; } if(root.data > nodeToBeInserted.data) { if(root.left==null) root.left=nodeToBeInserted; else insert(root.left,nodeToBeInserted); } else if(root.data < nodeToBeInserted.data) if(root.right==null) root.right=nodeToBeInserted; else insert(root.right,nodeToBeInserted); return root; }   public static void inOrder(TreeNode root) { if(root==null) return; inOrder(root.left); System.out.print(root.data+" "); inOrder(root.right); } public static void main(String[] args) {   // Creating a binary search tree TreeNode rootNode=createBinarySearchTree(); TreeNode node55=new TreeNode(55); boolean result=search(rootNode,node55); System.out.println("Searching for node 55 : "+result); System.out.println("---------------------------"); TreeNode node13=new TreeNode(13); TreeNode root=insert(rootNode,node13); System.out.println("Inorder traversal of binary tree after adding 13:"); inOrder(root);   }   public static TreeNode createBinarySearchTree() { TreeNode rootNode =new TreeNode(40); TreeNode node20=new TreeNode(20); TreeNode node10=new TreeNode(10); TreeNode node30=new TreeNode(30); TreeNode node60=new TreeNode(60); TreeNode node50=new TreeNode(50); TreeNode node70=new TreeNode(70); TreeNode node5=new TreeNode(5); TreeNode node55=new TreeNode(55);   insert(null,rootNode); insert(rootNode,node20); insert(rootNode,node10); insert(rootNode,node30); insert(rootNode,node60); insert(rootNode,node50); insert(rootNode,node70); insert(rootNode,node5); insert(rootNode,node55); return rootNode; }   }

When you run above program, you will get below output:

1 2 3 4 5 6

Searching for node 55 : true --------------------------- Inorder traversal of binary tree after adding 13: 5 10 13 20 30 40 50 55 60 70