Reverse in-order traversal of BST

 

Introduction

  How would you get sorted output from a binary tree ? In-order traversal. Recollect all the things that we studied about bst till now,

http://analgorithmaday.blogspot.com/2011/03/binary-search-treeinsertion.html

For BST insertion, we follow in-order principles to construct the nodes. We traverse left/right based on the value and reach the point where the value is greater or lesser. If its less than the root, its left else its right. So, we construct the tree in such a way that, left-root-right is done in reverse from top to bottom.

  But in in-order traversal, we come bottom to top from left->right. This order in which we do the recursion is very important.

  Now, we know that, if we do a in-order traversal of a BST, we get increasing order sorted array. How would you get a decreasing order? How quick sort can do decreasing order sort then ?

Concept

   Decreasing order sort in a quick sort is done by doing partition in a different way. When you partition the array with smaller elements in the left and larger elements at the right, you get increasing order sort. Similarly, if you keep the larger elements to the left and smaller elements to the right, you get decreasing order sort. In Quick sort, its just like changing the > symbol to <.

  But in BST, we have < and > based tree construction done already on memory. In Quick sort, its done on the run. So, how does BST-Sort do descending order sort then ? With in-order traversal.

Don’t mug up that, In-order means left-root-right. :)

You can also do right-root-left. :D It’s just the way of traversal, that’s it!! :)

This is called reverse in-order by some people. So, in a BST, if you do reverse in-order, you get descending order sorted array

Code

#include <stdlib.h>

#include <limits.h>

#include <math.h>

#include <iostream>

class BST {

public:

    int data;

    BST* parent;

    BST* left;

    BST* right;

};

BST* createBSTNode(int data)

{

    BST* newNode = new BST();

    newNode->data = data;

    newNode->left = NULL;

    newNode->right = NULL;

    newNode->parent = NULL;

    return newNode;

}

void bst_insert(BST*& tree, BST* node)

{

    BST* prev = NULL;

    BST* iter=tree;

    while(iter != NULL)

    {

        prev = iter;

        if(node->data < iter->data)

            iter = iter->left;

        else

            iter = iter->right;

    }

    // found node is parent to our node

    node->parent = prev;

    // if prev is NULL

    // then this is the first node

    // change the root NODE

    if(prev == NULL)

        tree = node;

    else {

        // now we need to decide where the node

        // should go: left or right

        if(node->data < prev->data)

            prev->left = node;

        else

            prev->right = node;

    }

}

BST* convert_arr_bst(int* arr, int size)

{

    BST* tree=NULL;

    for(int i=0;i<size;i++) {

        bst_insert(tree, createBSTNode(arr[i]));

    }

    return tree;

}

void ascending(BST* root)

{

    if(root == NULL) return;

    ascending(root->left);

    std::cout<<root->data<<" ";

    ascending(root->right);

}

void descending(BST* root)

{

    if(root == NULL) return;

    descending(root->right);

    std::cout<<root->data<<" ";

    descending(root->left);

}

void main()

{

    int A[] = {4,5,3,2,8,10,1,2};

    BST* root = convert_arr_bst(A, sizeof(A)/sizeof(int));

    ascending(root);

    std::cout<<std::endl;

    descending(root);

    std::cout<<std::endl;

}

• There are also some BST’s which instead of storing lesser elements at the left and greater at the right, it will do in reverse. Just change the < to > in bst_insert function. You can just do in-order traversal to get the descending order numbers.
• Now, we understand that, we can mirror a tree using reverse in-order. :) This is also one of the important interview question.
• Another important thing, you get in a binary search tree root. The median… The root most of the times divides the array into two. If its not, it becomes completely unbalanced.