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

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.

How to check a Linked-List is a Palindrome.

Solution Approach:

First thing is we should know about palindrome.

What is Palindrome?
The list must be the same backwards and forwards such as

0-> 1 -> 2->1->0 This leads us to our first solution.

This problem can solved in many ways,

1. Reverse and Compare
2. Iterative Approach
3. Recursive Approach

Among three i will first solve this problem using Iterative Approach just see the below 

Implementation:

public boolean isPalindrome(LinkedListNode head)

{

LinkedListNode fast =head;

LinkedListNode slow =head;

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

while(fast!=null && fast.next !=null)

{

 stack.push(slow.data);

 slow=slow.next;

 fast=fast.next.next;

 

}

if(fast!=null)

{

  slow =slow.next;

}

while(slow!=null)

{

int top=stack.pop().intValue();

if(top!=slow.data)

                {

   return false;

}

slow=slow.next;

}

return true;

}

Now you can try others too......

Given a circular linked list,implement an algorithm which returns the node at the beginning of the loop.

Solution Approach:

1. Create two pointers ,Fast Pointer and Slow Pointer.
2. Move Fast Pointer at a rate of 2 and slow pointer at rate of 1.
3. When they collide ,move slow pointer to linkedlisthead.keep fast pointer where it is.
4. Move slow pointer and fast pointer at a rate of one step.return the new collision point.

Implementation:

public LinkedListNode FindBeginning(LinkedListNode head)
{
LinkedListNode slow=head;
LinkedListNode fast=head;

while(fast! =null && fast.next !=null)
{
slow =slow.next;
fast=fast.next.next;
if(slow==fast){ // collision
break;
}
}

if(fast == null || fast.next == null)  // no metting point means no loop
return null;

slow=head;
while(slow!=fast)
{
slow=slow.next;
fast=fast.next;
}

}
return fast;


}

Flyweight Pattern example java

Flyweight reduces the cost of creating and manipulating a large number of similar objects.Flyweight is used when there is a need to create large number of objects which are in similar nature.Large number of objects consumes high memory and flyweight design pattern gives a solution to reduce the load on memory by sharing objects.It is achieved by isolating object properties into two types intrinsic and extrinsic .

Intrinsic and Extrinsic State:

Create only 25 objects for mapping every unique characters. these 26 objects will have intrinsic state as its character.that is object '"a" will have state as character "a" .then what happens to color ,font and size? those are the extrinsic state and will be passed by client code.26 objects will be in store;client code will get the needed character/object and pass the extrinsic state to it with respect to the context.with respect to context means '''a" in first line may com in red color and same character may com in blue in different line.

When to use Flyweight Design Pattern:

• Need to create large number of objects.
• Because of the large number when memory cost is a constraint.
• When most of the object attribute can be made external and shared.
• Its better when extrinsic state can be computed rather than stored.

Proxy Design Pattern in java tutorial

What is Proxy Design Pattern?

First of all its a structural pattern and Proxy means in place of.In our collage times we gave proxy in place of or on behalf of are literal meanings of proxy.There are many different flavors of proxy depending on its purpose.we may have a protection proxy to control access rights to an object.

For Example:

Let say you want to attach  an image with an e-mail .now suppose this email has to be sent to millions of consumers in an e-mail campaign.Attaching the image and sending along with the e-mail will be very heavy operation.

So what we can do instead send the image as a link to one of the servlet. The Place Holder of the image will be sent.Once the email reaches the consumer the image place holder will call the servlet and load the image at run time from server.

Now when to use Proxy Pattern:

It is used when we need to represent a complex object with a simpler one.If creation of object is expensive,its creation can be suspended till the necessity arises  and till then a simple object can represent it.The Simple Object is called the Proxy for the complex Object.

Implementation:

/**
 * @author Abhinaw.Tripathi
 *
 */

interface Image
{
 public void showImage();
}

class RealImage implements Image
{
public RealImage(URL url)
{
loadImage(url);
}
private void loadImage(URL url)
{
// operation to load image
}
@Override
public void showImage()
{
// TODO Auto-generated method stub
//display the image

}
}

class ProxyImage implements Image
{

private URL url;
public ProxyImage(URL url) {
this.url=url;
}


public ProxyImage(String string) {
// TODO Auto-generated constructor stub
}


@Override
public void showImage() {
// TODO Auto-generated method stub
RealImage real=new RealImage(url);
real.showImage();
}
 
}

public class ProxyPatternTest {

/**
*
*/
public ProxyPatternTest() {
// TODO Auto-generated constructor stub
}

/**
* @param args
*/
public static void main(String[] args) {
// TODO Auto-generated method stub

     Image img1=new ProxyImage("testfolder/image1.png");
     Image img2=new ProxyImage("testfolder/image2.png");
     img1.showImage();  // you can do something like this.
}

}