# Operations on Binary Search Trees (BST)

When we store ordered data in an array, we have a very efficient search algorithm, i.e. the binary searching. However, we have very inefficient insertion and deletion algorithms that require shifting data in the array. To provide efficient insertions and deletions, we developed the linked list. The problem with linked lists, however, is that their search algorithms are sequential searches, which are very inefficient. Binary trees offer short paths from root. A node has up to two children. Data is organized by value. Some of the operations that we’ll discuss in this article are given with brief description below:

**Insertion:**inserts an item into the tree**Search:**searches an item from the tree**Traversal:**traverses the tree**Deletion:**deletes an item from the tree**Find Minimum:**find the item that has the minimum value in the tree**Find Maximum:**find the item that has the maximum value in the tree**Print:**print the values of all items in the tree, using a traversal strategy that is appropriate for the application**Successor:**finds the next item in the tree w.r.t current**Predecessor:**finds the previous item in the tree w.r.t current

### Inserting an item in BST

void Insert(Node *&tree, int item) //’tree’ points to ‘root’ node in // the beginning { if(tree == NULL) { // base case tree = new Node; tree->right = NULL; tree->left = NULL; tree->data = item; } else if(item < tree->data) Insert(tree->left, item); else Insert(tree->right, item); }

### Finding minimum and maximum

The minimum element of BST is the left most node of left sub tree. Therefore the minimum can always be found by tracking the left child pointers until an empty sub tree is reached. If there is no left sub tree then minimum key is at root( i.e. key[ x])

Tree-Minimum(x) { while( x->left != NIL) x = x->left return x }

Tree-Maximum(x) { while( x->right != NIL) x = x->right return x }

### Traversing BST

Many applications require that all of the nodes of a tree be “visited”. Visiting a node may mean printing contents, retrieving information, making a calculation, etc. Traverse: To visit all the nodes in a tree in a systematic fashion.

There are mainly three ways to traverse a tree:

- In-order Traversal
- Post-order Traversal
- Pre-order Traversal

**1. In-order Traversal:**

Inorder(tree) If tree is not NULL Inorder(Left(tree)) Visit Info(tree) Inorder(Right(tree))

**2. Pre-order Traversal: **

Consider following example, this would be order of traversing in pre-order: J E A H T M Y

Preorder (tree) If tree is not NULL Visit Info(tree) Preorder(Left(tree)) Preorder(Right(tree))

**3. Post-order Traversal: **

Consider following example, this would be order of traversing in post-order: A H E M Y T J

Postorder (tree) If tree is not NULL Postorder(Left(tree)) Postorder(Right(tree)) Visit Info(tree)

## Exercise

Find:

- In-order ?
- Pre-order ?
- Post-order ?

### Searching the tree

Start at the root Is target = value at current node? We’re done Is target < value at current node? Yes: search left subtree No: search right subtree

When given a pointer to the root of a tree and a key, Tree-Search will return a pointer to the node with key k if there exists one. Suppose x = root.

Tree-Search (x, k) { if x=NIL or k= x->data return x if k < x->data return Tree-Search(x->left, k) else return Tree-Search( x->right, k) }

This function follows the BST property, if value of k is smaller than that of x, then it should be in left subtree of x, else it should be in right subtree of x.

### Successor Function

- If x has a right subtree, then successor(x) is the left most element in that sub tree.
- If x has no right sub tree, then successor(x) is the lowest ancestor of x (above x on the path to the root) that has x in its left sub tree.

- The successor of node with key 15 is node with key 17.
- The successor of node with key 7 is node with key 9.
- The successor of node with key 13 is node with key 15.

### Predecessor Function

- If x has a left sub tree, then the predecessor must be the right most element of the left sub tree.
- If x has no left sub tree, then predecessor (x) is the lowest ancestor of x (above x on the path to the root) that has x in its right sub tree.

- The predecessor of node with key 6 is node with key 4.
- The predecessor of node with key 15 is node with key 13.
- The predecessor of node with key 17 is node with key 15.

### Deleting from BST

First, find the item; then, delete it. Binary search tree property must be preserved!!

We need to consider three different cases:

- Deleting a leaf
- Deleting a node with only one child
- Deleting a node with two children

**1. Deleting a leaf**

**2. Deleting a node with only one child**

**3. Deleting a node with two children**

- Find predecessor (it is the rightmost node in the left subtree) OR Find successor (it is the leftmost node in the right subtree)
- Replace the data of the node to be deleted with predecessor/successor’s data
- Delete predecessor/successor node

void Delete(Node *&tree, int item) { if(item < tree->data) Delete(tree->left, item); else if(item > tree->data) Delete(tree->right, item); else DeleteNode(tree); }

void DeleteNode(Node *&tree) { int data; Node *tempPtr = tree; if(tree->left == NULL) { //right child tree = tree->right; delete tempPtr; } else if(tree->right == NULL) { // left child tree = tree->left; delete tempPtr; } else { GetPredecessor(tree->left, data); tree->data = data; Delete(tree->left, data); } }

void GetPredecessor(Node * tree, int &data) { while(tree->right != NULL) tree = tree->right; data = tree->data; }

### Related Posts

- Binary Trees and Binary Search Trees
- Advanced Data Structures Tutorial using C++
- Binary Search Trees and Data Structure
- Heap data structure in C++
- Implementing Stack Data Structure in C++
- Circular Linked Lists
- Data Structures Tutorial using C++
- Implementation of Priority Queue using Heap data structure in C++
- Binary Expression Trees
- Selection Sort: A Graphical Explanation
- Insertion Sort: A Graphical Explanation
- Applications of Stack in Data Structures

### Popular Posts (last 30 days)

- Applications of Stack in … 1142 view(s)
- Circular Linked Lists 1092 view(s)
- Attendance Management Sys… 951 view(s)
- Simple Currency Converter… 681 view(s)
- Finding Minimum, Maximum … 659 view(s)
- Implementing Stack Data S… 632 view(s)
- Recursive Factorial funct… 579 view(s)
- Graph Implementation in C… 576 view(s)
- Finding Maximum Number in… 430 view(s)
- GRASP Design Patterns 368 view(s)

### Related Links

### Tags

Android C-Sharp C/C++ language Classes Data structures Design Pattern Eclipse Game Development Graphics Design Books HTML iPhone JAVA JAVA GUI MIPS Assembly Mobile Programming Books Object Oriented PDF PHP Programming Programming Books Programming Languages Books Python RaphaelJS REST Source Code Threads Tutorial Web Development Books