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

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

How to check if a Binary Tree is BST or not?

What is Binary Search Tree(BST)?

A binary search tree (BST) is a node based binary tree data structure.

Must have these Properties:

• The left subtree of a node contains only nodes with keys less than the node’s key.
• The right subtree of a node contains only nodes with keys greater than the node’s key.
• Both the left and right subtrees must also be binary search trees.

Implementation:

/**

 * 

 */

package com.bst;

/**

 * @author Abhinaw.Tripathi

 *

 */

class Node

{

int data;

Node left,right;

public Node(int item)

{

this.data=item;

left=right=null;

}

}

public class BinaryTree

{

/**

* 

*/

private Node root;

public BinaryTree() 

{

// TODO Auto-generated constructor stub

}

public boolean isBSTUtil(Node node,int min,int max)

{

if(node == null)

return true;

if(node.data < min || node.data> max)

return false;

return (isBSTUtil(node.left, min, node.data-1) && isBSTUtil(node.right, node.data+1, max));

}

public boolean isBST()  

{

        return isBSTUtil(root, Integer.MIN_VALUE,Integer.MAX_VALUE);

    }

 

/**

* @param args

*/

public static void main(String[] args) 

{

// TODO Auto-generated method stub

BinaryTree tree = new BinaryTree();

        tree.root = new Node(4);

        tree.root.left = new Node(2);

        tree.root.right = new Node(5);

        tree.root.left.left = new Node(1);

        tree.root.left.right = new Node(3);

 

        if (tree.isBST())

        {

            System.out.println("IS BST");

        }

        else

        {

            System.out.println("Not a BST");

        }

}

}

Time Complexity: O(n)

Auxiliary Space : O(1) 

If Function Call Stack size is not valid, otherwise O(n)

To check if a binary tree is balanced.For this,a balanced tree is defined to be a tree such that the heights of the two sub-tree of any node never differ by more than one.

Solution Approach:

Point to be noted here is two sub tree differ in height by no more than one.So we can simply recurs through the entire tree,and for each node,compute the height of each sub tree.

Implementation:

public static int getHeight(TreeNode root)
{
if(root == null)
return 0;

return Math.max(getHeight(root.left), getHeight(root.right)) +1 ;
}

public static boolean isBalanced(TreeNode root)
{
if(root == null)
return 0;

int heightDiff=getHeight(root.left) - getHeight(root.right);
if(Math.abs(heightDiff) > 1)
{
return false;
}

else
{
return isBalanced(root.left) && isBalanced(root.right);
}

}

This solution is not that efficient.

Complexity will be o(Nlog N) because each node is touched once and getHeight is called repetedly on the same node.