Find k-th smallest element in BST (Order Statistics in BST)

Solution Approach:

By using In order traversal of BST retrieves elements of tree in the sorted order. The in order traversal uses stack to store to be explored nodes of tree (threaded tree avoids stack and recursion for traversal). The idea is to keep track of popped elements which participate in the order statics.

Implementation:

public int kthSmallest(TreeNode root, int k) 

{

    Stack<TreeNode> stack = new Stack<TreeNode>();

 

    TreeNode p = root;

    int res = 0;

 

    while(!stack.isEmpty() || p!=null)

{

        if(p!=null)

{

            stack.push(p);

            p = p.left;

        }

else

{

            TreeNode t = stack.pop();

            k--;

            if(k==0)

                res = t.val;

            p = t.right;

        }

    }

 

    return res;

}

We can in order traverse the tree and get the kth smallest element. 

Time complexity: O(n) where n is total nodes in tree.

Total number of possible Binary Search Trees with n keys?

Solution Approach:

Before going deeper,we should know about Catlan Number.
Here it is:

Total number of possible Binary Search Trees with n different keys = Catalan number Cn = (2n)!/(n+1)!*n!

For n = 0, 1, 2, 3, … values of Catalan numbers are 1, 1, 2, 5, 14, 42, 132, 429, 1430, 4862, …. So are numbers of Binary Search Trees.

Implementation:

/**
 *
 */
package com.bst;

/**
 * @author Abhinaw.Tripathi
 *
 */
public class NumberOfBinaryTree
{
   
    public int computePossibilities(int n, int[] solutions)
    {
       
        if (n < 0) return 0;
        else if ((n == 1) || (n == 0)) return 1;
       
        int possibilities = 0;
       
        for (int i = 0; i < n; i++)
        {
            if (solutions[i] == -1)
                solutions[i] = computePossibilities(i, solutions);
               
            if (solutions[n-1-i] == -1)
                solutions[n-1-i] = computePossibilities(n-1-i, solutions);
           
            possibilities += solutions[i]*solutions[n-1-i];
        }
       
        return possibilities;
    }
   
    public int numTrees(int n)
    {
       
        int[] solutions = new int[n];
       
        for (int i = 0; i < n; i++)
            solutions[i] = -1;
       
        return computePossibilities(n, solutions);
    }

   public static void main(String[] args)
   {
       NumberOfBinaryTree solution = new NumberOfBinaryTree();
       
       // print the total number of unique BSTs for n = 3
       System.out.println(solution.numTrees(3));
       
    // print the total number of unique BSTs for n = 4
       System.out.println(solution.numTrees(4));
   }
}