Binary Tree to Binary Search Tree Conversion

Following is a 3 step solution for converting Binary tree to Binary Search Tree.

1) Create a temp array arr[] that stores inorder traversal of the tree. This step takes O(n) time.

2) Sort the temp array arr[]. Time complexity of this step depends upon the sorting algorithm. In the following implementation, Quick Sort is used which takes (n^2) time. This can be done in O(nLogn) time using Heap Sort or Merge Sort.

3) Again do inorder traversal of tree and copy array elements to tree nodes one by one. This step takes O(n) time.

Solution:

/**
 *
 */
package com.bst;

/**
 * @author Abhinaw.Tripathi
 *
 */
import java.util.Arrays;
import java.util.LinkedList;

public class ConvertBinaryTreeToBST {
class QueueNode {
TreeNode treeNode;
int level;

QueueNode(TreeNode node, int level) {
this.treeNode = node;
this.level = level;
}
}

class TreeNode {
TreeNode left;
TreeNode right;
int value;

public TreeNode(int value) {
this.value = value;
}
}

TreeNode root;
int treeSize;

private TreeNode createTree() {
this.root = new TreeNode(0);
TreeNode n1 = new TreeNode(1);
TreeNode n2 = new TreeNode(2);
TreeNode n3 = new TreeNode(3);
TreeNode n4 = new TreeNode(4);
TreeNode n5 = new TreeNode(5);
TreeNode n6 = new TreeNode(6);
TreeNode n7 = new TreeNode(7);
TreeNode n8 = new TreeNode(8);

root.left = n1;
root.right = n2;

n1.left = n3;
n1.right = n4;

n2.left = n5;

n3.right = n6;

n5.right = n7;

n6.right = n8;

treeSize = 9;

return root;
}

public void printTreeLevelOrder() {
if (root == null)
return;

LinkedList queue = new LinkedList();
queue.add(new QueueNode(root, 0));

int maxLevelVisited = -1;

while (!queue.isEmpty()) {
QueueNode currentNode = (QueueNode) queue.remove();

if (currentNode.level > maxLevelVisited) {
maxLevelVisited = currentNode.level;
System.out.print("\nlevel-" + currentNode.level + " nodes: ");
}
System.out.print(" " + currentNode.treeNode.value);

if (currentNode.treeNode.left != null) {
queue.add(new QueueNode(currentNode.treeNode.left,
currentNode.level + 1));
}

if (currentNode.treeNode.right != null) {
queue.add(new QueueNode(currentNode.treeNode.right,
currentNode.level + 1));
}
}
}

private void createInorderArray(TreeNode currentNode, int[] inorder,
int[] index) {
if (currentNode == null) {
return;
}

createInorderArray(currentNode.left, inorder, index);

inorder[index[0]] = currentNode.value;
index[0] += 1;

createInorderArray(currentNode.right, inorder, index);
}

private void changeNodeValues(TreeNode currentNode, int[] inorder,
int[] index) {
if (currentNode == null) {
return;
}

changeNodeValues(currentNode.left, inorder, index);

currentNode.value = inorder[index[0]];
index[0] += 1;

changeNodeValues(currentNode.right, inorder, index);
}

public void changeTreeToBST() {
int[] inorder = new int[treeSize];
int[] index = new int[1];

createInorderArray(root, inorder, index);

Arrays.sort(inorder);

index[0] = 0;

changeNodeValues(root, inorder, index);
}

public static void main(String[] args) {
ConvertBinaryTreeToBST solution = new ConvertBinaryTreeToBST();

solution.createTree();

solution.changeTreeToBST();

System.out.print("Modified tree to BST: \n");

solution.printTreeLevelOrder();
}
}

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));
   }
}