• Skip to primary navigation
  • Skip to content
  • Skip to primary sidebar
  • Skip to footer
  • Core Java
  • Design Patterns
  • JSP
  • Servlets
  • Building Tools
  • jQuery
  • Spring
  • Hibernate
  • Mongo DB
  • More
    • HTML
    • SCJP
    • AJAX
    • UML
    • Struts
    • J2EE
    • Testing
    • Angular JS

J2EE Reference

  • Home
  • About Us
    • Java Learning Centers
  • Contact Us

Binary search tree implementation in java

May 18, 2017 By j2eereference Leave a Comment

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.

Java
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

Related Posts

  • Java Buzzwords
  • Anonymous Inner Class in Java
  • Network Programming – java.net Package
  • Java Regular Expressions
  • Method Local Inner Class in Java
  • URL Processing in Java
  • Difference between Stack and Heap memory
  • What is ThreadMXBean in java?
  • What is serialVersionUID
  • What is exchanger in concurrency?

Filed Under: Core Java Tagged With: Binary search Tree, Binary search tree creation, binary search tree property, Binary Tree

Reader Interactions

Leave a Reply Cancel reply

This site uses Akismet to reduce spam. Learn how your comment data is processed.

Primary Sidebar

FOLLOW US ONLINE

  • View J2eereference-166104970118637’s profile on Facebook
  • View j2eereference’s profile on Twitter
  • View j2eereference’s profile on LinkedIn

Subscribe by email

Recent posts

  • Java Buzzwords
  • Anonymous Inner Class in Java
  • Network Programming – java.net Package
  • Java Regular Expressions
  • Method Local Inner Class in Java
  • URL Processing in Java
  • Iterator Design Pattern Implementation using Java
  • Strategy Design Pattern Implementation using Java
  • Decorator Design Pattern
  • Adapter Design Pattern Implementation using Java
  • JSF Composite Components
  • JSF UI Components
  • What is JavaServer Faces (JSF)?
  • GOF Design Patterns
  • History and Need for Design Patterns

Footer

Core Java
Design Patterns
JSP
Servlets
HTML
Building Tools
AJAX
SCJP
jQuery
Testing
Spring
UML
Struts
Java Centers
Java Training
Home
About Us
Contact Us
Copyright © j2eereference.com. All right reserved.