If you want to practice data structure and algorithm programs, you can go through 100+ java coding interview questions.
Binary search tree is a special type of binary tree which have following properties.
- Nodes which are smaller than root will be in left subtree.
- Nodes which are greater than root will be right subtree.
- It should not have duplicate nodes
- Both left and right subtree also should be binary search tree.

- 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.

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