Binary Search Tree
DEFINITION
A binary tree in which the nodes are labeled with elements of an ordered dynamic
set and the following BST property is satisfied: all elements stored in the left subtree
of any node x are less than the element stored at x and all elements stored in the right
subtree of x are greater than the element at x.
Inorder traversal of a binary search tree always gives a sorted sequence of the values.
This is a direct consequence of the BST property. This provides a way of sorting a
given sequence of keys: first, create a BST with these keys and then do an inorder
traversal of the BST so created.
Note that the highest valued element in a BST can be found by traversing from the
root in the right direction all along until a node with no right link is found (we can call
that the rightmost element in the BST).
The lowest valued element in a BST can be found by traversing from the root in the
left direction all along until a node with no left link is found (we can call that the
leftmost element in the BST).
Search is straightforward in a BST. Start with the root and keep moving left or right
using the BST property. If the key we are seeking is present, this search procedure
will lead us to the key. If the key is not present, we end up in a null link.
Insertion in a BST is also a straightforward operation. If we need to insert an element
x, we first search for x. If x is present, there is nothing to do. If x is not present, then
our search procedure ends in a null link. It is at this position of this null link that x
will be included.
If we repeatedly insert a sorted sequence of values to form a BST, we obtain a
completely skewed BST. The height of such a tree is n - 1 if the tree has n nodes.
Thus, the worst case complexity of searching or inserting an element into a BST
having n nodes is O(n).
Construct a BST using 8, 3, 6,7,10,4,1,14,13
2) Construct a Binary search Tree using following node elements value 13, 3, 4, 12, 14,
10, 5, 1, 8, 2, 7, 9, 11, 6, 18 and perform Traversal.
In order Traverse: Left, Root, Right
1,2,3,4,5,6,7,8,9,10,11,12,13,14,18
Pre order Traverse: Root, Left, Right
13,3,1,2,4,12,10,5,8,7,6,9,11,14,18
Post order Traverse: Left, Right
2,1,6,7,9,8,5,11,10,12,4,3,18,14,13
BINARY SEARCH TREE PROGRAM
package Trees;
import [Link];
class TNode
{
int data;
TNode left,right;
TNode(int data)
{
[Link]=data;
left=right=null;
}
}
class BSTTree
{
TNode root;
BSTTree()
{
root=null;
}
public TNode insertNode(TNode root,int x)
{
if(root==null)
{
root=new TNode(x);
}
else if(x<=[Link])
[Link]=insertNode([Link],x);
else
[Link]=insertNode([Link],x);
return root;
}
public void preorder(TNode root)
{
if(root!=null)
{
[Link]([Link]);
preorder([Link]);
preorder([Link]);
}
}
public TNode deleteNode(TNode root,int key)
{
if (root==null)
return root;
if(key<[Link])
[Link]=deleteNode([Link],key);
else if(key>[Link])
[Link]=deleteNode([Link],key);
else
{
if([Link]==null)
return [Link];
else if([Link]==null)
return [Link];
[Link]=minValue([Link]);
[Link]=deleteNode([Link],[Link]);
}
return root;
}
public int minValue(TNode root)
{
while([Link]!=null)
{
root=[Link];
}
return [Link];
}
}
public class BSTDemo {
public static void main(String args[])
{
BSTTree b=new BSTTree();
Scanner s=new Scanner([Link]);
boolean repeat=true;
while(repeat)
{
[Link]("[Link] [Link] [Link] [Link]");
[Link]("enter your choice");
int choice=[Link]();
if(choice==1)
{
[Link]("enter value to be inserted");
int x=[Link]();
[Link]=[Link]([Link], x);
}
else if(choice==2)
{
[Link]([Link]);
}
else if(choice==3)
{
[Link]("enter value to be deleted");
int key=[Link]();
[Link]=[Link]([Link], key);
}
else if(choice==4)
repeat=false;
}
}
}