A binary search tree (BST), also called an ordered or sorted binary tree, which has the following property for node-based binary tree data structure i.e.

- The left subtree of a node contains only nodes with keys less than the node's key.
- The right subtree of a node contains only nodes with keys greater than the node's key.
- Both the left and right subtrees must also be binary search trees.

An algorithm is a step-by-step procedure to solve a problem by a computer in a given number of steps. The algorithm is written in human readable and understandable form. To search an element in a given array, it can be achieved by performing following algorithms:

- Linear search
- Binary search
- Hash search
- Binary search tree

We have gone through different terms such as binary tree, binary search, binary search tree at the time of exploring different searching algorithms. Let us understand them in a better way.

Binary Tree is a special data structure used for storing data with a condition that each node can have a maximum of two children. A node in a binary tree is a data structure that has an element, and a reference to two other binary trees, typically called the left and right subtrees.

Figure: Representation of a Binary tree with nodes.

**Need Assignment help with Binary tree; contact our online chat support. More Tutorial for Binary tree**

Binary Search is used to perform search in a sorted array. It performs the search by testing the middle element of the array. If it the middle element is too big, the process is repeated in the left half of the array, and the right half if the value of middle element is too small. By doing this the amount of space that needs to be searched is halved every time. The time taken to do so comes out to be O(log n).

Figure: Performing binary search for a target element 34.

**Our online assignment help tutors always ready for help you. More Tutorial for Binary Search**

Binary Search tree exhibits a special behavior i.e. the left child of the node should have value less than its parent's value and the right child of the node must have a value greater than its parent value. Searching in a binary tree is similar to searching in a hash table. It is usually slower if the tree is unbalanced to an extent.

Binary Search tree performs the search at the root. After searching the root, it goes down to the left subtree if the value of the element at root is too big and the right subtree if is too small. Then, repeat the process until we find the target element in the tree or the sub-tree we want is not present in the tree. The time taken to run binary search tree is O(log n) on average and O(n) in the worst case.

Tree resulting from the following insertions: 38, 13, 51, 10, 12, 40, 84, 25, 89, 37, 66, 95

Figure: Performing insertion on binary search tree.

Now, let us understand the basic operations on Binary search tree with their algorithms.

The binary tree search algorithm start searching for the target element from the root node. If the value of element found is less than the key value, search for the element in the left subtree. Otherwise, search for the element in the right subtree of the tree. The algorithm is repeated for each of the node in the tree.

We will use the following procedure to search for a node with a given key or target value in a binary search tree.

Given a pointer to the root of the tree and a target element t,

TREE-SEARCH returns a pointer to a node with target element t if one exists; otherwise, it returns NIL.

**TREE-SEARCH (x, t)**

1ifp = NIL or t = key[p] 2then returnp 3ift < key[p] 4then returnTREE-SEARCH (left[p], t) 5else returnTREE-SEARCH (right[p], t)

To insert an element in a binary search tree, first locate its proper location. The binary tree starts searching for the target node from the root node. If the value of the data is less than the key value, it searches for an empty location in the left subtree and insert the data. Otherwise, search for the empty location in the right subtree and insert the data.

To insert a new element or value v into a binary search tree T, we will use the procedure TREE-INSERT.

The procedure passes a node z for which key[z] = v, left[z] = NIL, and right[z] = NIL. It modifies T and some of the fields of z in such a way that z is inserted into an appropriate position in the tree.

**TREE-INSERT (T, z)**

1 y ←NIL2 x ← root[T] 3whilex ≠ NIL 4doy ← x 5ifkey[z] < key[x] 6thenx ← left[x] 7elsex ← right[x] 8 p[z] ← y 9ify = NIL 10thenroot[T]← z 11else ifkey[z] < key[y] 12thenleft[y] ← z 13elseright[y]← z

A given node z from a binary search tree can be deleted by taking as an argument a pointer to z.

The procedure consists of the following three cases.

- If z contains no children, its parent p[z] is modified to replace z with NIL as its child.
- If the node contains a single child, we interconnect z by making a new link between its child and its parent.
- If the node contains two children, we connect out z's successor y, which has no left child and replace the contents of z with the contents of y.

**TREE-DELETE (T, z)**

1ifleft[z] = NIL or right[z] = NIL 2 then y ← z 3elsey ← TREE-SUCCESSOR(z) 4ifleft[y] ← NIL 5thenx ← left[y] 6elsex ← right[y] 7ifx ≠ NIL 8thenp[x] ← p[y] 9ifp[y] = NIL 10thenroot[T] ← x 11else ify = left[p[y]] 12thenleft[p[y]] ← x 13elseright[p[y]] ← x 14ify ≠ z 15thenkey[z] ← key[y] 16 If y has other fields, copy them, too. 17 ⊳returny

In the Pre-order traversal method, the root node is visited first and then the left subtree and finally the right subtree.

1 void preorder(Node *root){ 2 if(root){ 3 printf("%d", root->data); 4 preorder(root->left); 5 preorder(root->right); 6 } 7 }

In the In-order traversal method, the left subtree of the binary tree is visited first and then the root and later the right sub-tree. Always remember that every node may represent a subtree itself in a binary tree.

void inorder(Node *root){ if(root){ inorder(root->left); printf("%d", root->data); inorder(root->right); } }

In the Post-order traversal method, the root node is visited last. First, we traverse the left subtree and then the right subtree and finally the root node of the tree.

1 void postorder(Node *root){ 2 if(root){ 3 postorder(root->left); 4 postorder(root->right); 5 printf("%d", root->data); 6 } 7 }

To search a key element in a binary search tree.

PROGRAM:#include< iostream> #include< conio.h> #include< stdlib.h> using namespace std; void insert(int,int ); void delte(int); void display(int); int search(int); int search1(int,int); int tree[40],t=1,s,x,i; main() { int ch,y; for(i=1;i<40;i++) tree[i]=-1; while(1) { cout <<"1.INSERT AN ELEMENT\n2.DELETE AN ELEMENT\n3.DISPLAY ELEMENTS\n4.SEARCH AN ELEMENT\n5.EXIT\nEnter your choice:"; cin >> ch; switch(ch) { case 1: cout <<"Enter value of the element to insert in the tree"; cin >> ch; insert(1,ch); break; case 2: cout <<"Enter value of the element to delete from the tree"; cin >>x; y=search(1); if(y!=-1) delte(y); else cout<<"no such element in tree"; break; case 3: display(1); cout<<"\n"; for(int i=0;i<=32;i++) cout << i; cout <<"\n"; break; case 4: cout <<"enter the element to search:"; cin >> x; y=search(1); if(y == -1) cout <<"no such element in tree"; else cout << x << "is in" << y <<"position"; break; case 5: exit(0); } } } void insert(int s,int ch ) { int x; if(t==1) { tree[t++]=ch; return; } x=search1(s,ch); if(tree[x]>ch) tree[2*x]=ch; else tree[2*x+1]=ch; t++; } void delte(int x) { if( tree[2*x]==-1 && tree[2*x+1]==-1) tree[x]=-1; else if(tree[2*x]==-1) { tree[x]=tree[2*x+1]; tree[2*x+1]=-1; } else if(tree[2*x+1]==-1) { tree[x]=tree[2*x]; tree[2*x]=-1; } else { tree[x]=tree[2*x]; delte(2*x); } t--; } int search(int s) { if(t==1) { cout <<"no element in tree"; return -1; } if(tree[s]==-1) return tree[s]; if(tree[s]>x) search(2*s); else if(tree[s]< x) search(2*s+1); else return s; } void display(int s) { if(t==1) {cout <<"no element in tree:"; return;} for(int i=1;i<40;i++) if(tree[i]==-1) cout <<" "; else cout << tree[i]; return ; } int search1(int s,int ch) { if(t==1) { cout <<"no element in tree"; return -1; } if(tree[s]==-1) return s/2; if(tree[s] > ch) search1(2*s,ch); else search1(2*s+1,ch); }

Java Program to Implement a Binary Search Tree using Linked Lists.

PROGRAM:import java.util.Scanner; class Node { Node left, right; int data; public Node(int n) { left = null; right = null; data = n; } } class BST { private Node root; public BST() { root = null; } public void insert(int data) { root = insert(root, data); } private Node insert(Node node, int data) { if (node == null) node = new Node(data); else { if (data <= node.data) node.left = insert(node.left, data); else node.right = insert(node.right, data); } return node; } public void inorder() { inorder(root); } private void inorder(Node r) { if (r != null) { inorder(r.left); System.out.print(r.data +" "); inorder(r.right); } } public void preorder() { preorder(root); } private void preorder(Node r) { if (r != null) { System.out.print(r.data +" "); preorder(r.left); preorder(r.right); } } public void postorder() { postorder(root); } private void postorder(Node r) { if (r != null) { postorder(r.left); postorder(r.right); System.out.print(r.data +" "); } } } public class LinkedListBST { public static void main(String[] args) { Scanner scan = new Scanner(System.in); BST bst = new BST(); System.out.println("Linked List Binary Search Tree Test\n"); char ch; do { System.out.println("Enter integer element to insert"); bst.insert( scan.nextInt() ); System.out.print("\nPost order : "); bst.postorder(); System.out.print("\nPre order : "); bst.preorder(); System.out.print("\nIn order : "); bst.inorder(); System.out.println("\nDo you want to continue (Type y or n) \n"); ch = scan.next().charAt(0); } while (ch == 'Y'|| ch == 'y'); } }

To schedule a **Binary Search Tree ** tutoring session Click here

To submit **Binary Search Tree Assignments** Click here

The ** Assignment Help Services** that we provide include: Binary Search Tree, Computer Programming, Data Structure, Trees Assignment Help, Binary Search Tree Project Help and Binary Search Tree Tutorials.

Basic Subject

Computer Science

- Programming Assignment Help
- Database Help
- Data Structure Assignment Help
- Operating Systems Assignment Help
- Computer Network Assignment Help
- UML Diagram Assignment Help
- IT Assignment Help
- Game Programming
- Computer Science Assignment Help
- Medical Science Assignment Help
- Social Science Assignment Help
- Information Systems

Engineering

- Biochemical and Biotechnology Help
- Chemical Engineering Assignment
- Statistics Assignment Help
- Civil Engineering Assignment Help
- Electrical, Electronics Help
- Mathematics, Computing Assignment Help
- Mechanical and Industrial Engg. Help
- Petroleum Engg. Assignment Help
- Biochemistry Assignment Help
- Cell Biology Assignment Help
- Arts and Architecture Help
- Silverlight Assignment Help