# Binary Search Trees and Data Structure

Binary Search Trees (BSTs) are an important data structure for dynamic sets. Binary trees offer short paths from root. A node has up to two children that is why it is called binary tree. Data in binary tree is organized by value. A node in binary tree has following elements: A *key (value)* an identifying field inducing a total ordering; *left* pointer to a left child (may be NULL); *right* pointer to a right child (may be NULL); *p* pointer to a parent node (NULL for root). A Binary Search Tree satisfy following property:

key[leftSubtree(x)] £ key[x] £ key[rightSubtree(x)]

Following operations may be performed on Binary search tree:

- Traversal ( In-order, Pre-order, Post-order)
- Search
- Insertion
- Sorting
- Deletion

In this tutorial, we’ll see how a binary search tree will look like and then we’ll perform the above mentioned operations on it and see its usefulness.

An example of binary search tree is given below in following picture:

## 1) Traversing a BST

Traversing a tree means visiting all the nodes in a tree in a systematic fashion. Visiting a node may mean printing contents, retrieving information, making a calculation, etc. There are mainly three ways to traverse a tree:

### a) In-order Traversal

It prints left, then root, then right node. Also known as LNR where L is left, N is root and R is right. In-order tree traversal is used to display data in ascending order.

### b) Post-order Traversal

It prints left, then right, then root. Also known as LRN where L is left, N is root and R is right. Post-order tree traversal is used to destroy a BST.

### c) Pre-order Traversal

It prints root, then left, then right. Also known as NLR where L is left, N is root and R is right. Pre-order tree traversal is used in copying a binary search tree.

## 2) Searching a BST

To search a target value in BST is easy. To search any value, start at the root and test for target = value at current node. If target is equal to the current node value, then value is found we’re done searching. Otherwise test for target < value at current node. If target is less than current node, then search left sub-tree. If target is greater than current node, then search right sub-tree.

BST Search Algorithm TreeSearch(x, k) { if (x = NULL or k = key[x]) return x; if (k < key[x]) return TreeSearch(left[x], k); else return TreeSearch(right[x], k); }

## 3) Insertion in BST

In insertion, an element is added to the current BST. Let’s say, we want to add an element x to the tree such that the binary search tree property continue to hold.

The basic algorithm could be built taking following procedure:

- Insert x in place of NULL
- Use a “trailing pointer” to keep track of where you came from (like inserting into singly linked list)

Suppose we want to add C node in the following tree. Then following path (shown in red color) will be taken to insert a node C to the existing BST.

## 4) Sorting in BST

As discussed above, that in-order tree traversal is used to display BST in ascending order. Building a binary tree and then printing that tree in in-order can be used as a sorting algorithm. This algorithm can be compared with Quick sort algorithm. We’ll see both Quick sort and BST Sorting are actually similar algorithm. The only difference is in the data structure of the two algorithms.

**Informal code for sorting array A of length n with BST**

BSTSort(A) { for i=1 to n TreeInsert(A[i]); InorderTreeWalk(root); }

In above picture, we see same partitions are done as with Quick sort, but in a different order. In previous example, everything was compared to 3 once. Then those items < 3 were compared to 1 once etc. Same comparisons are done in BST as in Quick sort. For example, consider inserting 5. Since run time is proportional to the number of comparisons, which is same time as Quick sort that is O(n lg n). *Which do you think is better, quicksort or BSTSort? * The Answer is Quick sort because it has better constants; it sorts in place and doesn’t need to build data structure.

## 5) Delete in BST

For deletion, we will need a Successor() operation. And a Successor operation has following rules:

Two cases:

- x has a right subtree: successor is minimum node in right subtree
- x has no right subtree:
*successor*is the lowest**ancestor**of*x*(above x on the path to the root) that has*x*in its left sub tree.

Now keeping in mind the above successor operation, we can build a Delete operation in BST.

Three cases:

- x has no children:
- Remove x
- x has one child:
- Splice out x
- x has two children:
- Swap x with successor
- Perform case 1 or 2 to delete it

### Related Posts

- Introduction to Tree Data Structure
- Binary Trees and Binary Search Trees
- Heap data structure in C++
- Graph search in C++
- Advanced Data Structures Tutorial using C++
- Binary Expression Trees
- Operations on Binary Search Trees (BST)
- Introduction to Graph data structure
- Circular Linked Lists
- Heap Sort with Graphical Explanation
- Doubly Linked Lists
- Queues in C++

### 2 Responses to *Binary Search Trees and Data Structure*

### Leave a Reply Cancel reply

### Popular Posts (last 30 days)

- Attendance Management Sys… 1185 view(s)
- Graph Implementation in C… 587 view(s)
- Implementing Stack Data S… 578 view(s)
- Circular Linked Lists 524 view(s)
- Applications of Stack in … 523 view(s)
- Simple Currency Converter… 442 view(s)
- GRASP Design Patterns 328 view(s)
- Advanced Data Structures … 265 view(s)
- C++ Tutorial for Intermed… 253 view(s)
- Sockets and Network Progr… 185 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

b) Post-order Traversal

It prints root, then left, then right. Also known as NLR where L is left, N is root and R is right. Post-order tree traversal is used to destroy a BST.

Above definition is wrong.

In-oder

1. Visit LEFT recursively

2. Visit node

3. Visit RIGHT recursively

Pre-Order

1. Visit node

2. Visit LEFT recursively

3. Visit RIGHT recursively

Post-Order

1. Visit LEFT recursively

2. Visit RIGHT recursively

3. Visit node

Thank you for pointing out the mistake, Ningareddy. I have updated the post now.