This post introduces about Binary Search Tree in Java, both of concept and implementation. Binary Search Tree is a binary tree data structure allows us to maintain a sorted list of numbers. Let’s dig deeper.
Binary Search Tree in Java
Properties of Binary Search Tree
- The left subtree of a node has only nodes with keys lesser than its data.
- The right subtree of a node has only nodes with keys greater than its data.
- The left and right subtree must be a binary search tree too and there are no duplicate nodes.
Advantages: as you see the above image of Binary Search Tree. There is an ordering among nodes so that some operations can be done fast like search, minimum and maximum.
Searching a node in binary search tree
Now, I suppose that we are searching for a node with a given data. First, we must compare its data with the root node’s data. If the root contains that given data we return root. If the root node’s data is greater than that given data. We recur for the left subtree of the root node. Otherwise, we recur for the right subtree. Let’s have a look at the below implementation.
|
1 2 3 4 5 6 7 8 9 10 11 12 13 |
//searching a given data in Binary Search Tree public Node searchNode(Node root, int data) { // root node contains data if (root==null || root.data==data) return root; // a given data is less than root's data if (root.data > data) return searchNode(root.left, data); // a given data is greater than root's data return searchNode(root.right, data); } |
Insert a node in binary search tree
Inserting a value in the correct position is similar to searching because we must maintain the rule that left subtree is lesser than root and right subtree is larger than root. You certainly start from root till you hit a leaf node. Once a leaf node is found, the new node is added as a child of the leaf node. And a new node is always inserted at leaf.
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 |
/* A recursive method to insert a new data in BST */ Node insertRec(Node root, int data) { // If the tree is empty, create a new node if (root == null) { root = new Node(data); return root; } // If not, recur down the tree if (data < root.data) root.left = insertRec(root.left, data); else if (data > root.data) root.right = insertRec(root.right, data); return root; } |
A complete implementation of Binary Search Tree in Java
This program demonstrates both the searching and insertion methods above.
|
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 |
// Node binary tree class Node { int data; Node left, right; public Node(int item) { data = item; left = right = null; } } // A program to demonstrate search and insert operation class SimpleBST { // Root node Node root; // Constructor SimpleBST() { root = null; } //searching a given data in Binary Search Tree public Node searchNode(Node root, int data) { // root node contains data if (root==null || root.data==data) return root; // a given data is less than root's data if (root.data > data) return searchNode(root.left, data); // a given data is greater than root's data return searchNode(root.right, data); } /* A recursive method to insert a new data in BST */ Node insertNode(Node root, int data) { // If the tree is empty, create a new node if (root == null) { root = new Node(data); return root; } // If not, recur down the tree if (data < root.data) root.left = insertNode(root.left, data); else if (data > root.data) root.right = insertNode(root.right, data); return root; } /* Visit its nodes in inorder - (left,root,right)*/ void visitInorder(Node node) { if (node == null) return; //1. First recur on left child visitInorder(node.left); //2. Print the left current node System.out.print(node.data + " "); //3. Recur on right child visitInorder(node.right); } // Main method public static void main(String[] args) { SimpleBST tree = new SimpleBST(); tree.root = tree.insertNode(tree.root,60); tree.root = tree.insertNode(tree.root,20); tree.root = tree.insertNode(tree.root,10); tree.root = tree.insertNode(tree.root,40); tree.root = tree.insertNode(tree.root,70); tree.root = tree.insertNode(tree.root,60); tree.root = tree.insertNode(tree.root,80); tree.root = tree.insertNode(tree.root,30); // print inorder traversal of the BST tree.visitInorder(tree.root); //search a node Node node = tree.searchNode(tree.root, 70); System.out.println("\nSearch result is: "+node.data); } } |
Here is the output of the above program
That’s all about Binary Search Tree in Java.
References
Binary Tree Data Structure in Java
Binary Tree Java Documentation
