Sorted order printing of a given array that represents a BST

Sorted order printing of a given array that represents a BST

Given an array that stores a complete Binary Search Tree, write a function that efficiently prints the given array in ascending order.

For example, given an array [4, 2, 5, 1, 3], the function should print 1, 2, 3, 4, 5

http://www.geeksforgeeks.org/sorted-order-printing-of-an-array-that-represents-a-bst/

BST with node equals sum of all greater nodes

Given a BST, convert it so that each node has value equal to sum of all the nodes (including itself) which are greater than that node in the whole tree.

Construct BST from preorder traversal

Given preorder traversal of a binary search tree, construct the BST.

For example, if the given traversal is {10, 5, 1, 7, 40, 50}, then the output should be root of following tree.

     10
   /   \
  5     40
 /  \      \
1    7      50

http://www.geeksforgeeks.org/construct-bst-from-given-preorder-traversa/
http://algorithms.tutorialhorizon.com/construct-binary-search-tree-from-a-given-preorder-traversal-using-recursion/
http://algorithms.tutorialhorizon.com/construct-binary-search-tree-from-a-given-preorder-traversal-using-stack-without-recursion/

Variation 1:
Given the Pre-order of the BST .check if each non-leaf node has only one child.Linear Time is expected.


Method 1 ( O(n^2) time complexity )
The first element of preorder traversal is always root. We first construct the root. Then we find the index of first element which is greater than root. Let the index be ‘i’. The values between root and ‘i’ will be part of left subtree, and the values between ‘i+1′ and ‘n-1′ will be part of right subtree. Divide given pre[] at index “i” and recur for left and right sub-trees.
For example in {10, 5, 1, 7, 40, 50}, 10 is the first element, so we make it root. Now we look for the first element greater than 10, we find 40. So we know the structure of BST is as following.

             10
           /    \
          /      \
  {5, 1, 7}       {40, 50}
We recursively follow above steps for subarrays {5, 1, 7} and {40, 50}, and get the complete tree.

Code:

#include <stdio.h>
#include <stdlib.h>

struct node
{
    int data;
    struct node *left;
    struct node *right;
};

struct node* newNode (int data)
{
    struct node* temp = (struct node *) malloc( sizeof(struct node) );

    temp->data = data;
    temp->left = temp->right = NULL;

    return temp;
}

struct node* constructTreeUtil (int pre[], int* preIndex,
                                int low, int high, int size)
{
    // Base case
    if (*preIndex >= size || low > high)
        return NULL;

    // The first node in preorder traversal is root. So take the node at
    // preIndex from pre[] and make it root, and increment preIndex
    struct node* root = newNode ( pre[*preIndex] );
    *preIndex = *preIndex + 1;

    // If the current subarry has only one element, no need to recur
    if (low == high)
        return root;

    // Search for the first element greater than root
    int i;
    for ( i = low; i <= high; ++i )
        if ( pre[ i ] > root->data )
            break;

    // Use the index of element found in postorder to divide postorder array in
    // two parts. Left subtree and right subtree
    root->left = constructTreeUtil ( pre, preIndex, *preIndex, i - 1, size );
    root->right = constructTreeUtil ( pre, preIndex, i, high, size );

    return root;
}

struct node *constructTree (int pre[], int size)
{
    int preIndex = 0;
    return constructTreeUtil (pre, &preIndex, 0, size - 1, size);
}

void printInorder (struct node* node)
{
    if (node == NULL)
        return;
    printInorder(node->left);
    printf("%d ", node->data);
    printInorder(node->right);
}

int main ()
{
    int pre[] = {10, 5, 1, 7, 40, 50};
    int size = sizeof( pre ) / sizeof( pre[0] );

    struct node *root = constructTree(pre, size);

    printf("Inorder traversal of the constructed tree: \n");
    printInorder(root);
    getchar();

    return 0;
}
Time Complexity: O(n^2)

Method 2 ( O(n) time complexity )
The idea used here is inspired from method 3 of this post. The trick is to set a range {min .. max} for every node. Initialize the range as {INT_MIN .. INT_MAX}. The first node will definitely be in range, so create root node. To construct the left subtree, set the range as {INT_MIN …root->data}. If a values is in the range {INT_MIN .. root->data}, the values is part part of left subtree. To construct the right subtree, set the range as {root->data..max .. INT_MAX}.

Code:

#include <stdio.h>
#include <stdlib.h>
#include <limits.h>

struct node
{
    int data;
    struct node *left;
    struct node *right;
};

struct node* newNode (int data)
{
    struct node* temp = (struct node *) malloc( sizeof(struct node) );

    temp->data = data;
    temp->left = temp->right = NULL;

    return temp;
}

struct node* constructTreeUtil( int pre[], int* preIndex, int key,
                                int min, int max, int size )
{
    // Base case
    if( *preIndex >= size )
        return NULL;

    struct node* root = NULL;

    // If current element of pre[] is in range, then
    // only it is part of current subtree
    if( key > min && key < max )
    {
        // Allocate memory for root of this subtree and increment *preIndex
        root = newNode ( key );
        *preIndex = *preIndex + 1;

        // Contruct the subtree under root

        // All nodes which are in range {min .. key} will go in left
        // subtree, and first such node will be root of left subtree.
        root->left = constructTreeUtil( pre, preIndex, pre[*preIndex],
                                        min, key, size );

        // All nodes which are in range {key..max} will go in right 
        // subtree, and first such node will be root of right subtree.
        root->right = constructTreeUtil( pre, preIndex, pre[*preIndex],
                                         key, max, size );
    }

    return root;
}

struct node *constructTree (int pre[], int size)
{
    int preIndex = 0;
    return constructTreeUtil ( pre, &preIndex, pre[0], INT_MIN, INT_MAX, size );
}

void printInorder (struct node* node)
{
    if (node == NULL)
        return;
    printInorder(node->left);
    printf("%d ", node->data);
    printInorder(node->right);
}

int main ()
{
    int pre[] = {10, 5, 1, 7, 40, 50};
    int size = sizeof( pre ) / sizeof( pre[0] );

    struct node *root = constructTree(pre, size);

    printf("Inorder traversal of the constructed tree: \n");
    printInorder(root);
    getchar();

    return 0;
}

Time Complexity: O(n)

Variation 1:
http://www.careercup.com/question?id=14453690

Permutations of BST

Given an array of integers arr = [5,6,1].

When we construct a BST with this input in the same order, we will have "5" as root, "6" as the right child and "1" as left child.

Now if our input is changed to [5,1,6], still our BST structure will be identical.

So given an array of integers, how to find the number of different permutations of the input array that results in the identical BST as the BST formed on the original array order?

Startegy:

Your question is equivalent to the question of counting the number of topological orderings for the given BST.

For example, for the BST

  10
 /  \
5   20
 \7 | \
    15 30

the set of topological orderings can be counted by hand like this: 10 starts every ordering. The number of topological orderings for the subtree starting with 20 is two: (20, 15, 30) and (20, 30, 15). The subtree starting with 5 has only one ordering: (5, 7). These two sequence can be interleaved in an arbitrary manner, leading to 2 x 10 interleavings, thus producing twenty inputs which produce the same BST. The first 10 are enumerated below for the case (20, 15, 30):

 10 5 7 20 15 30
 10 5 20 7 15 30
 10 5 20 15 7 30
 10 5 20 15 30 7
 10 20 5 7 15 30
 10 20 5 15 7 30
 10 20 5 15 30 7
 10 20 15 5 7 30
 10 20 15 5 30 7
 10 20 15 30 5 7

The case (20, 30, 15) is analogous --- you can check that any one of the following inputs produces the same BST.

This examples also provides a recursive rule to calculate the number of the orderings. For a leaf, the number is 1. For a non-leaf node with one child, the number equals to the number of topological orderings for the child. For a non-leaf node with two children with subtree sizes |L| and |R|, both having l and r orderings, resp., the number equals to

  l x r x INT(|L|, |R|)

Where INT is the number of possible interleavings of |L| and |R| elements. This can be calculated easily by (|L| + |R|)! / (|L|! x |R|!). For the example above, we get the following recursive computation:

  Ord(15) = 1
  Ord(30) = 1
  Ord(20) = 1 x 1 x INT(1, 1) = 2  ; INT(1, 1) = 2! / 1 = 2
  Ord(7) = 1
  Ord(5) = 1
  Ord(10) = 1 x 2 x INT(2, 3) = 2 x 5! / (2! x 3!) = 2 x 120 / 12 = 2 x 10 = 20

Useful Link:

http://stackoverflow.com/questions/1701612/permutations-of-bst?rq=1

Binary Tree to BST Conversion

Given a Binary Tree, convert it to a Binary Search Tree. The conversion must be done in such a way that keeps the original structure of Binary Tree.

Example 1--------------
Input:
          10
         /  \
        2    7
       / \
      8   4
Output:
          8
         /  \
        4    10
       / \
      2   7


Example 2---------------
Input:
          10
         /  \
        30   15
       /      \
      20       5
Output:
          15
         /  \
       10    20
       /      \
      5        30

http://www.geeksforgeeks.org/binary-tree-to-binary-search-tree-conversion/

Correct the BST !

Two nodes of a BST are swapped, correct the BST
September 14, 2012
Two of the nodes of a Binary Search Tree (BST) are swapped. Fix (or correct) the BST.

Input Tree:
         10
        /  \
       5    8
      / \
     2   20

In the above tree, nodes 20 and 8 must be swapped to fix the tree.
Following is the output tree
         10
        /  \
       5    20
      / \
     2   8

Strategy:

The inorder traversal of a BST produces a sorted array. So a simple method is to store inorder traversal of the input tree in an auxiliary array. Sort the auxiliary array. Finally, insert the auxiilary array elements back to the BST, keeping the structure of the BST same. Time complexity of this method is O(nLogn) and auxiliary space needed is O(n).

We can solve this in O(n) time and with a single traversal of the given BST. Since inorder traversal of BST is always a sorted array, the problem can be reduced to a problem where two elements of a sorted array are swapped. There are two cases that we need to handle:

1. The swapped nodes are not adjacent in the inorder traversal of the BST.

 For example, Nodes 5 and 25 are swapped in {3 5 7 8 10 15 20 25}.
 The inorder traversal of the given tree is 3 25 7 8 10 15 20 5
If we observe carefully, during inorder traversal, we find node 7 is smaller than the previous visited node 25. Here save the context of node 25 (previous node). Again, we find that node 5 is smaller than the previous node 20. This time, we save the context of node 5 ( current node ). Finally swap the two node’s values.

2. The swapped nodes are adjacent in the inorder traversal of BST.

  For example, Nodes 7 and 8 are swapped in {3 5 7 8 10 15 20 25}.
  The inorder traversal of the given tree is 3 5 8 7 10 15 20 25
Unlike case #1, here only one point exists where a node value is smaller than previous node value. e.g. node 7 is smaller than node 8.

How to Solve? We will maintain three pointers, first, middle and last. When we find the first point where current node value is smaller than previous node value, we update the first with the previous node & middle with the current node. When we find the second point where current node value is smaller than previous node value, we update the last with the current node. In case #2, we will never find the second point. So, last pointer will not be updated. After processing, if the last node value is null, then two swapped nodes of BST are adjacent.

Code:

#include <stdio.h>
#include <stdlib.h>

struct node
{
    int data;
    struct node *left, *right;
};

void swap( int* a, int* b )
{
    int t = *a;
    *a = *b;
    *b = t;
}

struct node* newNode(int data)
{
    struct node* node = (struct node *)malloc(sizeof(struct node));
    node->data = data;
    node->left = NULL;
    node->right = NULL;
    return(node);
}

// This function does inorder traversal to find out the two swapped nodes.
// It sets three pointers, first, middle and last.  If the swapped nodes are
// adjacent to each other, then first and middle contain the resultant nodes
// Else, first and last contain the resultant nodes
void correctBSTUtil( struct node* root, struct node** first,
                     struct node** middle, struct node** last,
                     struct node** prev )
{
    if( root )
    {
        // Recur for the left subtree
        correctBSTUtil( root->left, first, middle, last, prev );

        // If this node is smaller than the previous node, it's violating
        // the BST rule.
        if (*prev && root->data < (*prev)->data)
        {
            // If this is first violation, mark these two nodes as
            // 'first' and 'middle'
            if ( !*first )
            {
                *first = *prev;
                *middle = root;
            }

            // If this is second violation, mark this node as last
            else
                *last = root;
        }

        // Mark this node as previous
        *prev = root;

        // Recur for the right subtree
        correctBSTUtil( root->right, first, middle, last, prev );
    }
}

// A function to fix a given BST where two nodes are swapped.  This
// function uses correctBSTUtil() to find out two nodes and swaps the
// nodes to fix the BST
void correctBST( struct node* root )
{
    // Initialize pointers needed for correctBSTUtil()
    struct node *first, *middle, *last, *prev;
    first = middle = last = prev = NULL;

    // Set the poiters to find out two nodes
    correctBSTUtil( root, &first, &middle, &last, &prev );

    // Fix (or correct) the tree
    if( first && last )
        swap( &(first->data), &(last->data) );
    else if( first && middle ) // Adjacent nodes swapped
        swap( &(first->data), &(middle->data) );

    // else nodes have not been swapped, passed tree is really BST.
}

void printInorder(struct node* node)
{
    if (node == NULL)
        return;
    printInorder(node->left);
    printf("%d ", node->data);
    printInorder(node->right);
}

int main()
{
    /*   6
        /  \
       10    2
      / \   / \
     1   3 7  12
     10 and 2 are swapped
    */

    struct node *root = newNode(6);
    root->left        = newNode(10);
    root->right       = newNode(2);
    root->left->left  = newNode(1);
    root->left->right = newNode(3);
    root->right->right = newNode(12);
    root->right->left = newNode(7);

    printf("Inorder Traversal of the original tree \n");
    printInorder(root);

    correctBST(root);

    printf("\nInorder Traversal of the fixed tree \n");
    printInorder(root);

    return 0;
}
Output:

Inorder Traversal of the original tree
1 10 3 6 7 2 12
Inorder Traversal of the fixed tree
1 2 3 6 7 10 12
Time Complexity: O(n)

http://www.geeksforgeeks.org/fix-two-swapped-nodes-of-bst/

Reconstruct BST again !

All elements of a BST are multiplied by -1. Convert it to a BST once again.

Subtree in a BST with maximum sum

Find a sub tree in a BST such that the sub tree has maximum sum.

Strategy:
Sum of a tree is the sum of all the nodes of that tree. We have to find a sub-tree whose sum is maximum. Clearly, this tree has negative elements as well otherwise the question is trivial and the original tree itself is the answer.
 
Code:
#include <stdio.h>
#include <stdlib.h>

struct node
{
    int data;
    struct node *left;
    struct node *right;
};

//typedef tree node;

void insert(struct node *& root,int item){
     if(root==NULL){
          struct node *r= (struct node*)malloc(sizeof(struct node));
          r->data=item;
          r->left=NULL;
          r->right=NULL;
          root=r;
          return;
     }
     if (item< root->data){
        insert(root->left,item);
        return;
     }
     else{
        insert(root->right,item);
        return;
     }
     return;
}

int maxSum(struct node* root, int* max)
{
    if(root == NULL)
        return 0;

    int sum = maxSum(root->left, max) + maxSum(root->right, max) + root->data;

    if(sum > *max)
        *max = sum;

    return sum;
}

int main()
{
    struct node *root=NULL;

    insert(root, -10);
    insert(root, -20);
    insert(root, 30);
    insert(root, -5);
    insert(root, 40);

    int max=0;

    maxSum(root, &max);
    printf("maxSum = %d\n", max);

    return 0;
}

Single Child BST or Not

Check if each internal node of a BST has exactly one child

Given Preorder traversal of a BST, check if each non-leaf node has only one child. Assume that the BST contains unique entries.

Examples

Input: pre[] = {20, 10, 11, 13, 12}
Output: Yes
The give array represents following BST. In the following BST, every internal
node has exactly 1 child. Therefor, the output is true.
        20
       /
      10
       \
        11
          \
           13
           /
         

http://www.geeksforgeeks.org/check-if-each-internal-node-of-a-bst-has-exactly-one-child/

Number streams are same BSTs or Not

You are given 2 number streams. You need to find whether they will create the same BST or not.

Example:
Array1:10 5 20 15 30
Array2:10 20 15 30 5
Result: True

Array1:10 5 20 15 30
Array2:10 15 30 20 5
Result: False[As per diagram below]

                       10                                                                             10
                   /        \                                                                       /          \
                 5         20                                                                   5           15
                          /      \                                                                                  \
                         15     30                                                                               30
                                                                                                                     /
                                                                                                                   20

Print BST keys within a given range

Given two values k1 and k2 (where k1 < k2) and a root pointer to a Binary Search Tree. Print all the keys of tree in range k1 to k2. i.e. print all x such that k1<=x<=k2 and x is a key of given BST. Print all the keys in increasing order.
For example, if k1 = 10 and k2 = 22, then your function should print 12, 20 and 22.
                                       20
                                   /         \
                                 8           22
                             /     \
                           4      12
http://www.geeksforgeeks.org/print-bst-keys-in-the-given-range/

Strategy:

1) If value of root’s key is greater than k1, then recursively call in left subtree.
2) If value of root’s key is in range, then print the root’s key.
3) If value of root’s key is smaller than k2, then recursively call in right subtree.

Note:Here k1 is min value and k2 is max value in the range given

Code: 

void PrintBSTKeys(struct node *root, int k1, int k2)

{

   if ( NULL == root )

      return;

   if ( k1 < root->data )

     PrintBSTKeys(root->left, k1, k2)

   if ( k1 <= root->data && k2 >= root->data )

     printf("%d ", root->data );

   if ( k2 > root->data )

     PrintBSTKeys(root->right, k1, k2);

}
Time Complexity:O(n)

Populate Inorder successor in BST

Given a Binary Search Tree where each node has following structure, write a function to populate next pointer for all nodes. The next pointer for every node should be set to point to inorder successor.

struct node {   int data;   struct node* left;   struct node* right;   struct node* next; }

Initially, all next pointers have NULL values. Your function should fill these next pointers so that they point to inorder successor.

Method 1:Reverse Inorder Traversal

Traverse the given tree in reverse inorder traversal and keep track of previously visited node. When a node is being visited, assign previously visited node as next.

void populateNextRecur(struct tree* node, struct tree *&next_ref)
{
    if (node)
    {
        populateNextRecur(node->right, next_ref);

        node->next = next_ref;

        next_ref = node;

        populateNextRecur(node->left, next_ref);
    }
}

void populateNext(struct tree *root)
{
    struct tree *next = NULL;
    populateNextRecur(root, next);
}

Remove Duplicate nodes in BST/BT

Write A Program to Remove Duplicates from BST.

Strategy:

Assuming if duplicate is there in inserting in a BST we put that in the left.
So 2 cases are there :
1.duplicate is the left child of its replica.
2.duplicate is at the successor position of the node.

Pseudo Code:

func(Node *node)
  {
    if(!node)
    return;

if(isduplicateexist(node))
   {
    dupparent=find_dup_parent(node);
    if(dupparent ! =node)
      {
       dup=dupparent->right;
      dupparent->right=dupparent->right->left;
      }
  else
   {
    dup=node->left;
    node->left=node->left->left;
   }

del (dup);
}
func(node->left);
func(node->right);
}

Remove Duplicates from BT.
http://www.mycareerstack.com/question/155/

kth largest /smallest element in a BST

How to find kth smallest element in BST. you cannot use static/global variable and you cannot pass value of k to any function ?

http://www.geeksforgeeks.org/find-k-th-smallest-element-in-bst-order-statistics-in-bst/

Using static variable:

Traverse the tree in descending order and keep a count of number of nodes visited. 

When this count is equal to 'k', print the element. 

void printk(struct node* root, int k)
{
    if(root == NULL)
        return;
    static int index = 0;
    printk(root->right, k);

    if(++index == k)
    {
        printf("%d\n", root->data);
        return;
    }
    printk(root->left, k);
}

Code:

#include <stdio.h>
#include <stdlib.h>
#include <limits.h>

struct node
{
int data;
struct node* left;
struct node* right;
};

struct node* newNode(int data)
{
struct node* node = (struct node*)
malloc(sizeof(struct node));
node->data = data;
node->left = NULL;
node->right = NULL;

return(node);
}

struct node* insert(struct node* node, int data)
{

if (node == NULL)
return(newNode(data));
else
{
if (data <= node->data)
node->left = insert(node->left, data);
else
node->right = insert(node->right, data);


return node;
}
}

int kthMax(struct node* t, int *k) {

if(t == NULL)
return INT_MIN;

int x = kthMax(t->right, k);

if(x != INT_MIN) return x;

(*k)--;
if(*k == 0) return t->data;

return kthMax(t->left, k);
}

int kthMin(struct node* t, int *k) {

if(t == NULL)
return INT_MAX;

int x = kthMin(t->left, k);

if(x != INT_MAX) return x;

(*k)--;
if(*k == 0) return t->data;

return kthMin(t->right, k);
}

int main()
{
struct node* root = NULL;
root = insert(root, 4);
insert(root, 2);
insert(root, 1);
insert(root, 3);
insert(root, 6);
insert(root, 5);

int n=2,m=3;
printf("Given kth Min in BST is %d \t kth Max is=%d", kthMin(root,&n),kthMax(root,&m));
getchar();
return 0;
}

Pending

Pending

Tree Traversal based Questions

Post Order

http://www.geeksforgeeks.org/given-a-binary-tree-how-do-you-remove-all-the-half-nodes/

Pre Order

1. http://www.dsalgo.com/2013/03/find-deepest-nodes-of-binary-tree.html

2. http://www.geeksforgeeks.org/check-if-a-binary-tree-is-subtree-of-another-binary-tree/

http://www.geeksforgeeks.org/check-binary-tree-subtree-another-binary-tree-set-2/

3. Trim a BST

http://www.geeksforgeeks.org/remove-bst-keys-outside-the-given-range/
http://www.ardendertat.com/2012/01/17/programming-interview-questions-26-trim-binary-search-tree/

4.

In Order:

1. Pair of values in BST with sum S

http://www.geeksforgeeks.org/find-a-pair-with-given-sum-in-bst/

http://www.geeksforgeeks.org/find-if-there-is-a-triplet-in-bst-that-adds-to-0/

2. Median in a BST

https://learn.hackerearth.com/forum/354/median-of-a-bst/

3. BST to Greater Sum Tree/

http://algorithms.tutorialhorizon.com/convert-bst-to-greater-sum-tree/

4. kth smallest or largest in a BST

http://www.geeksforgeeks.org/find-k-th-smallest-element-in-bst-order-statistics-in-bst/
http://www.geeksforgeeks.org/kth-largest-element-in-bst-when-modification-to-bst-is-not-allowed/
http://www.geeksforgeeks.org/kth-smallest-element-in-bst-using-o1-extra-space/

Level Order:

1. http://www.geeksforgeeks.org/find-minimum-depth-of-a-binary-tree/

2.http://www.geeksforgeeks.org/check-if-a-given-binary-tree-is-complete-tree-or-not/
http://www.geeksforgeeks.org/check-whether-binary-tree-complete-not-set-2-recursive-solution/

3.http://www.geeksforgeeks.org/print-cousins-of-a-given-node-in-binary-tree/

4. 

Successor/Predecessor Rules in BST/BT

Write programs to find inorder successor and inorder predecessor of a binary search tree

Also find

i)preorder sucessor and  preorder predecessor

ii)postorder successor and postorder predecessor

Given a Binary Tree and a key, write a function that prints all the ancestors of the key in the given binary tree. 

For example, if the given tree is following Binary Tree and key is 7, then your function should print 4, 2 and 1.

              1
            /   \
          2      3
        /  \
      4     5
     /
    7

Inorder successor of BST:

Method 1:Without Parent Pointer-Search from Root

1) If right subtree of node is not NULL, then succ lies in right subtree. Do following.

Go to right subtree and return the node with minimum key value in right subtree.

2) If right sbtree of node is NULL, then start from root and us search like technique. Do following.

Travel down the tree, if a node’s data is greater than root’s data then go right side, otherwise go to left side

Code:

.

struct node * inOrderSuccessor(struct node *root, struct node *n)

{

    if( n->right != NULL )

        return minValue(n->right);

    struct node *succ = NULL;

    while (root != NULL)    //Start from the root

    {

        if (n->data < root->data)

        {

            succ = root;

            root = root->left;

        }

        else if (n->data > root->data)

            root = root->right;

        else

           break;

    }

    return succ;

}

Time Complexity:O(h)-h is height of tree

References:http://net.pku.edu.cn/~course/cs101/2007/resource/Intro2Algorithm/book6/chap13.htm

Method 2:With Parent Pointer 

1) If right subtree of node is not NULL, then succ lies in right subtree. Do following.
Go to right subtree and return the node with minimum key value in right subtree.
2) If right sbtree of node is NULL, then succ is one of the ancestors. Do following.
Travel up using the parent pointer until you see a node which is left child of it’s parent. The parent of such a node is the succ.

Code:

struct node

{

    int data;

    struct node* left;

    struct node* right;

    struct node* parent;

};

struct node * inOrderSuccessor(struct node *root, struct node *n)

{

  if( n->right != NULL )

    return minValue(n->right);

  struct node *p = n->parent;

  while(p != NULL && n == p->right)

  {

     n = p;

     p = p->parent;

  }

  return p;

}

struct node * minValue(struct node* node) {

  struct node* current = node;

  while (current->left != NULL)   //Leftmost node

{  

    current = current->left;

  }

  return current;

}

Time Complexity:O(h) 

Inorder Predecessor of BST:

Method 1:Start from Root
struct node * inOrderPredecessor(struct node *root, struct node *n)
{
if( n->left != NULL )
return maxValue(n->left);
struct node *pred=NULL;
while(root)
{
if(n->data < root->data)
root=root->left;
else if(n->data > root->data)
{
pred=root;
root=root->right;
}
else
break;
}
return pred;
}
Time:O(logn) in Avg. & O(N) in worst

Method 2:Using Parent

1.Find The Minimum value in BSt if given Node has the same value we are done as
the minimum value in BST is left most leaf & can't have any predecessor :)
2.Check if node->Left is leaf or not if yes then node->left is our answer
3.if n is right child then its parent will be inorder predecessor
4.else if all above case fail then inorder predecessor be maximum value in left
subtree of given node N.

Code:
struct node
{
int data;
struct node* left;
struct node* right;
struct node* parent;
};

struct node* minValue(struct node* node);

int isLeaf(struct node* root)
{
if(root->left==NULL && root->right==NULL)
return 1;
return 0;
}

struct node* maxValue(struct node* node)
{
struct node* current = node;

 while (current->right!= NULL)  //loop down to find the leftmost leaf
{
current = current->right;
}
return current;
}

struct node* inOrderPredecessor(struct node *root, struct node *n)
{
// step 1 of the above algorithm

if(n==minValue(root))
{
printf("No Inorder Predecessor Possible");
return NULL;
}

//2nd step of above algo

if(isLeaf(n->left))
return n->left;

//3rd step if n is right children of parent

struct node *p =n->parent;
if(n == p->right)
return p;

// step 4 of the above algorithm if all above not satisfied then predecessor exist in right
return maxValue(n->left);
}
Time Complexity:O(logn) Time in Avg.Case & O(N) time in Worst Case Skew Tree

Sorted Array/Linked List to Balanced BST & BST to Circular Doubly Linked List

1st Question: Sorted Array to BST

Examples:

Input:  Array {1, 2, 3} or 1->2->3
Output: A Balanced BST
     2
   /  \
  1    3 

Input: Array {1, 2, 3, 4} or 1->2->3->4
Output: A Balanced BST
      3
    /  \
   2    4
 /
1

http://www.geeksforgeeks.org/sorted-array-to-balanced-bst/
http://www.geeksforgeeks.org/sorted-linked-list-to-balanced-bst/

Also

1.Convert Sorted Doubly Linked List to Binary Tree- http://discuss.joelonsoftware.com/default.asp?interview.11.465953.9

Usage:

1.BST to Min-Heap
http://www.geeksforgeeks.org/in-place-convert-bst-into-a-min-heap/
2.Merge 2 BSTs
http://www.geeksforgeeks.org/merge-two-balanced-binary-search-trees/

2nd Question: BST/BT to Circular Doubly Linked List

http://articles.leetcode.com/convert-binary-search-tree-bst-to/
http://www.geeksforgeeks.org/in-place-convert-a-given-binary-tree-to-doubly-linked-list/
http://www.geeksforgeeks.org/convert-a-given-binary-tree-to-doubly-linked-list-set-2/
http://www.geeksforgeeks.org/convert-given-binary-tree-doubly-linked-list-set-3/


Also


1. Convert a BST to circular sorted linked list-http://www.careercup.com/question?id=123685

LCA in a Binary Tree or BST

1. LCA in a Binary Search Tree.

http://www.geeksforgeeks.org/lowest-common-ancestor-in-a-binary-search-tree/
http://articles.leetcode.com/lowest-common-ancestor-of-a-binary-search-tree/

2. LCA in a Binary Tree.

http://www.geeksforgeeks.org/lowest-common-ancestor-binary-tree-set-1/
http://articles.leetcode.com/lowest-common-ancestor-of-a-binary-tree-part-i

Parent PointerApproach:
http://www.geeksforgeeks.org/lowest-common-ancestor-in-a-binary-tree-set-2-using-parent-pointer/
http://articles.leetcode.com/lowest-common-ancestor-of-a-binary-tree-part-ii

RMQ Approach:
http://www.geeksforgeeks.org/find-lca-in-binary-tree-using-rmq/

3. Minimum Distance between two nodes in a BST/BT
http://www.geeksforgeeks.org/find-distance-two-given-nodes/
http://algorithms.tutorialhorizon.com/find-the-distance-between-two-nodes-of-a-binary-tree/

BST Operations: Insert, Search, Delete - Recursive and Iterative

Write functions in C for following BST operations

1.  Search-both iterative and recursive

2. INSERT_BST- both iterative & recursive

3. DELETE_BST

Recursive:

http://quiz.geeksforgeeks.org/binary-search-tree-set-1-search-and-insertion/
http://quiz.geeksforgeeks.org/binary-search-tree-set-2-delete/
http://quiz.geeksforgeeks.org/data-structure/binary-search-trees/

Iterative:

void Search_BST_Iterative(int item,struct node *root,struct node *&par,struct node *&loc)
{
struct node *ptr,*ptrsave;
       if(root==NULL) //Tree EMPTY
         {  loc=NULL;
            par=NULL;
            return;
         }
       if(item==root->data) //Item is at root
         {  loc=root;
            par=NULL;
            return;
         }
       //Initialise ptr & ptrsave
        
         if(item<root->data)
                 ptr=root->left;
         else
                 ptr=root->right;
         ptrsave=root;

         while(ptr!=NULL)
         {   
            if(item==ptr->data)
              {   loc=ptr;
                  par=ptrsave;
                   return;
              }
            ptrsave=ptr;
            if(item<ptr->data)
                ptr=ptr->left;
            else
                ptr=ptr->right;
         }
loc=NULL; //ITEM NOT FOUND
par=ptrsave;
}

Insert_BST_Iterative:

void INSERT_BST_Iterative(struct node *&root,int item)
{struct node *tmp,*parent,*location;
tmp=(struct node*)malloc(sizeof(struct node));
tmp->data=item;
tmp->left=NULL;
tmp->right=NULL;
Search_BST_Iterative(item,root,parent,location);
if(location!=NULL)
    {printf("Data already present");
     return;
    }
if(parent==NULL)
    root=tmp;
else
    if(item<parent->data)
        parent->left=tmp;
    else
        parent->right=tmp;
}

Runtimes:

Both the BST search and insert algorithms share the same running time: log₂ n in the best case, and linear in the worst case. The insert algorithm's running time mimics the search's because it essentially uses the same tactics used by the search algorithm to find the location for the newly inserted node.

While binary search trees ideally exhibit sub-linear running times for insertions, searches, and deletions, the running time is dependent upon the BST's topology. The topology, as we discussed in the Inserting Nodes into a BST section, is dependent upon the order with which the data is added to the BST. Data being entered that is ordered or near-ordered will cause the BST's topology to resemble a long, thin tree, rather than a short, wide one. In many real-world scenarios, data is naturally in an ordered or near-ordered state.

The problem with BSTs is that they can become easily unbalanced. A balanced binary tree is one that exhibits a good ratio of breadth to depth. As we will examine in the next part of this article series, there are a special class of BSTs that are self-balancing. That is, as new nodes are added or existing nodes are deleted, these BSTs automatically adjust their topology to maintain an optimal balance. With an ideal balance, the running time for insertion, searches, and deletion, even in the worst case, is log₂ n. 

Delete BST Iterative:

void case_a(struct node *&root,struct node *par,struct node *loc)
{    if(par==NULL)
        root=NULL;
    else
        if(loc==par->left)
            par->left=NULL;
        else
            par->right=NULL;
}

void case_b(struct node *&root,struct node *par,struct node *loc)
{struct node *child;
//Initialaise CHILD
if(loc->left!=NULL)
    child=loc->left;
else
    child=loc->right;
if(par==NULL)
    root=child;
else
    if(loc==par->left)
        par->left=child;
    else
        par->right=child;
}   

void case_c(struct node *&root,struct node *&par,struct node *&loc)
{
     struct node *ptr,*ptrsave,*suc,*parsuc;
     ptrsave=loc;
     ptr=loc->right;
    while(ptr->left!=NULL)
    {    ptrsave=ptr;
        ptr=ptr->left;
    }
suc=ptr;
parsuc=ptrsave;

if(suc->left==NULL && suc->right==NULL)
                   case_a(root,parsuc,suc);
else
                   case_b(root,parsuc,suc);

if(par==NULL)
    root=suc;
else
    if(loc==par->left)
        par->left=suc;
    else
        par->right=suc;
   
    suc->left=loc->left;
    suc->right=loc->right;
}      

void DELETE_BST_Iterative(struct node *& root,int data)
{struct node *parent,*location;
 if(root==NULL)
{printf("Tree Empty");
 return;}Search_BST_Iterative(data,root,parent,location);
if(location==NULL)
{printf("DATA Not Present in Tree");
 return;}

if(location->left==NULL && location->right==NULL)
    case_a(root,parent,location);
if(location->left!=NULL && location->right==NULL)
    case_b(root,parent,location);
if(location->left==NULL && location->right!=NULL)
    case_b(root,parent,location);
if(location->left!=NULL && location->right!=NULL)
    case_c(root,parent,location);
free(location);
}

Useful Links on BST:
Java Version:
http://algorithms.tutorialhorizon.com/binary-search-tree-complete-implementation/

http://msdn.microsoft.com/en-us/library/aa289150(v=vs.71).aspx