Binary Search Tree: Binary search tree is a hierarchical data structure which is used to store data.In a binary tree each node has maximum of two children.Binary Search tree shows a special feature given below:
- Value of Left child node should be less than its parent’s node value
- Value of right child node should be greater than its parent’s node value.
Important terms used in Binary tree:
- Root :Topmost node of the tree is called root node.
- Child Node: Child node is a node which is below a given node and connected through an edge in downward direction.
- Parent Node : Any node except root node which is above a given node and connected through an edge in upward direction.
- Leaf : Leaf node is the node which does not have any children
- Keys : Key represents value of a node.
- Path : Path represents sequence of nodes along the edges.
- Levels : Root node is at level 0 and next child node is at Level 1 ,so Level represents height of tree from the root node.
- Visiting : checking the value of node during traversal.
Binary search Tree implementation in Java
In the below program , we will implement Binary search tree using Java.
newNode() method will insert node in the binary tree, first inserted node is root node which is 6 in our example. Inside newNode() method we are checking whether new node value is less than or greater than root node value 6. If it is greater than 6 then keep this node at the left side of root node 6 otherwise keep the given node at the right side. In this way we are calling newNode method recursively to check and insert the given node at the correct place.
printTree() method will first print left nodes then root node and then right node using recursion.
|
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 |
class Node { public int data; public Node left; public Node right; } public class BinaryTree { static Node newNode(int data, Node node) { if(node==null) { node = new Node(); node.data = data; node.left = null; node.right=null; return node; } else { Node current=node; if(data >=current.data) { current.right= newNode(data,current.right); } else if(data < current.data) { current.left=newNode(data,current.left); } } return node; } static void printTree(Node root) { if(root!=null) { printTree(root.left); System.out.print(root.data +" "); printTree(root.right); } } public static void main(String[] args) { Node rootNode = null; rootNode=newNode(6, rootNode); rootNode=newNode(2, rootNode); rootNode=newNode(3, rootNode); rootNode=newNode(8, rootNode); rootNode=newNode(7, rootNode); rootNode=newNode(1, rootNode); rootNode=newNode(5, rootNode); rootNode=newNode(10, rootNode); printTree(rootNode); } } |
Output:
1 2 3 5 6 7 8 10
6 is root node
Type of Traversals in binary Tree:
- Preorder Traversal– In Preorder traversal, first of all root node is visited then traverse the left subtree and at last traverse the right subtree
Visit Root–>Left Subtree traversal –> Right Tree Traversal
For binary tree given in above example,Preorder would be 6,1,2,3,5,7,8,10
- Inorder Traversal− In Inorder traversal, traverse the left subtree then visit the root node and at last traverse the right subtree
Left Subtree traversal –>Visit Root–>Right Tree Traversal
For binary tree given in above example,Preorder would be 1,2,3,5,6,7,8,10
- Postorder Traversal− − In Postorder traversal, traverse the right then visit the traverse the left subtree and at last visit the root node.
Right Tree Traversal->Left Subtree traversal –>Visit Root
For binary tree given in above example,Preorder would be 7,8,10,1,2,3,5,6
Use cases of Binary Search Tree:
1)Binary Search Tree is used in Search applications like dictionary
2) It is used in multilevel indexing in database
Leave a Reply