1. Write an algorithm to find the second smallest element in a Binary Search Tree. The simplest algorithm according to CLRS would be returning the parent of the minimum.

Ans:

1) Create an empty stack S.
2) Initialize current node as root
3) Push the current node to S and set current = current->left until current is NULL
4) If current is NULL and stack is not empty then 
     a) Pop the top item from stack and add the popped_item to a result_array.
     b) Print the popped item, set current = popped_item->right 
     c) Go to step 3.
5) If current is NULL and stack is empty then we are done.
6) result_array[2] = second smallest node.
(Assuming array index starts from 1)


Stack S = new Stack();
current = root;

while(current != null){
     current = current.left;
     S.push(current);
}

while(current == null && (S is not empty)){
     result_array = insertInArray(S.pop());
     current = popped_item.right;
     if(current != null){
          current = current.left;
          S.push(current);
     }
}

Print second_smallest node (result_array[2])
** Assumption array index starts from 1 **

1. Write recursive version (pseudocode) of TREE-MINIMUM and TREE-SUCCESSOR.

Tree- Minimum

findMinBST(root){
    if(root == null){
        return -1;
    }
    else if(root.left == null){
        return root;
    }
    return findMinBST(root.left)
}

Successor code:
The Algorithm is divided into two cases on the basis of right subtree of the input node being empty or not.

Input: node, root // node is the node whose Inorder successor is needed.
output: succ // succ is Inorder successor of node.

Case 1: Node has right subtree:
Go to the left-most node in the right subtree. Meaning get the minimum key value in the right subtree.

case 2: Node has no right subtree:
Go to the nearest ancestor for which the given node would be the its left subtree.


recursive implementation
successor(x, node)
if(node.element <= x{
    // current <=x, so successor must be in right subtree
    if (node.right = null)
        return null
    else
        return successor(x, node.right)
}
else{
    // current >x, so successor is either in left subtree or current itself
    if (node.left = null){
        // if there is nothing on the left, it's certainly the current element
        return node.element
    }
    else{
        // there is a left subtree, so the successor is the minimum of the successor of the
        // left subtree, if any and the current node
        recurse ← successor(x, node.left)
        if (recurse = null)
            return node.element
        else
            return min(recurse, node.element)
    }
}

Give the recursive version of TREE-INSERT routine in BST.(Pseudocode or C/C++/Java/Python code is acceptable)

InsertBST(Node root, Key k)
if (root == null) // insertion position found
   return new Node(k);
if (k <= root.key){ // proceed to the left branch
   root.left = Insert(root.left, k);
}
else // k > root.key, i.e. proceed to the right branch
   root.right = Insert(root.right, k);
return root;

Postfix:
(AB+)*(C+D)
(AB+)*(CD+)
AB+CD+*

Prefix:
(+AB)*(C+D)
(+AB)*(+CD)
*+AB+CD

Infix:
The expression is already in Infix notation.
(A+B) *(C+D)