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:

  1. Traversal ( In-order, Pre-order, Post-order)
  2. Search
  3. Insertion
  4. Sorting
  5. 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);
            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

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:

  1. x has a right subtree: successor is minimum node in right subtree
  2. 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:

  1. x has no children:
    1. Remove x
  2. x has one child:
    1. Splice out x
  3. x has two children:
    1. Swap x with successor
    2. Perform case 1 or 2 to delete it
Tagged with: C/C++ languageData structures

2 Responses to Binary Search Trees and Data Structure

  1. Ningareddy says:

    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.

    1. Visit LEFT recursively
    2. Visit node
    3. Visit RIGHT recursively

    1. Visit node
    2. Visit LEFT recursively
    3. Visit RIGHT recursively

    1. Visit LEFT recursively
    2. Visit RIGHT recursively
    3. Visit node

Leave a Reply

Your email address will not be published.

You may use these HTML tags and attributes: <a href="" title=""> <abbr title=""> <acronym title=""> <b> <blockquote cite=""> <cite> <code> <del datetime=""> <em> <i> <q cite=""> <strike> <strong>


Looking for something?

Use the form below to search the site:

Still not finding what you're looking for? Drop a comment on a post or contact us so we can take care of it!

Related News Feeds

Set your Twitter account name in your settings to use the TwitterBar Section.