Binary Search Tree

 Binary Search Tree

Tree

Tree is a non-linear data structure. Data is stored in nodes of the tree. A node of a tree can have 0, 1, 2 or more children. The first element of the tree is known as the root of the tree and search or traveral of tree starts from the root.

Binary Tree

Binary Tree is tree in which a node can have 0, 1 or 2 children only. A node of binary tree has three fields: data, left and right; left and right fields of a node are of type node and store reference of another node (child node). Visiting each node of tree once is known as Tree Traversal. There are different types of tree traversals:

• Inorder
• Preorder
• Postorder

Binary Search Tree (BST)

Binary Search Tree is a binary tree in which elements are organized using following rule:

• Elements at the left to the root is less than or equal to element at the root
• Elements at the right of the root is greater than the element at the root
• Inorder traveral of the binary search tree results elements in ascending order
• Sub trees are also binary search tree

Creating a binary search tree:

import java.util.Scanner;

class binarytreenode{

            int data;

            binarytreenode left,right;

            public binarytreenode(){

                        left = null;

                        right = null;

            }

            public binarytreenode(int data){

                        this.data = data;

                        left = null;

                        right = null;

            }         

}

class binarytree{

                        public binarytreenode root=null, temp;

                        public binarytree(){

                                    root = null;

                                    temp = null;                                    

                        }

                        public void insertnode(binarytreenode newnode){

                                    if(root == null){

                                                root = newnode;

                                                System.out.println("Root Created!");

                                    }else{

                                                temp = root;

                                                while(temp != null){

                                                             if(temp.data < newnode.data){

                                                                         if(temp.right == null){

                                                                                     temp.right = newnode;

                                                                                     System.out.println("Child Created!");

                                                                                     break;

                                                                         }else{

                                                                                     temp = temp.right;

                                                                         }

                                                             }

                                                             else if(temp.data > newnode.data){

                                                                         if(temp.left == null){

                                                                                     temp.left = newnode;

                                                                                     System.out.println("Child Created!");

                                                                                     break;

                                                                         }else{

                                                                                     temp = temp.left;

                                                                         }

                                                             }                                                        

                                                }

                                    }

                        }

}