Program to find whether the binary tree is BST ?


A binary tree is binary search tree (BST) if :

  • If the left subtree nodes value is less than the given node.
  • If the right subtree nodes value is greater than the give node
  • Both the left and right subtrees are BST.

public class BinaryTreeIsBST {

	public boolean IsBST(TreeNode node, int max, int min){

		if(node == null)
			return true;
		if(min < node.value && node.value > max){
			return IsBST(node.left,min,node.value) &&
                         IsBST(node.right,node.value,max);
		}
		return false;
	}
}

Node.js :500 Error: Cannot find module ‘ejs’


Well, this is the day i am starting to learn node.js with web framework express. I will be updating the posts on regular basis for node.js.

IF you run node app.js

and get following error

500¬†Error: Cannot find module ‘ejs’

  • at Function.Module._resolveFilename (module.js:338:15)
  • at Function.Module._load (module.js:280:25)
  • at Module.require (module.js:364:17

Then you missed install express framework.

Just do

npm install ejs -g

-g is for global install.

Cheers !!

Write a program to find whether a binary tree is a balanced ?


As per wikipedia

A balanced binary tree is commonly defined as a binary tree in which the depth of the left and right subtrees of every node differ by 1 or less.

A binary tree can be considered as balanced if

  • The Left subtree is balanced
  • The right subtree is balanced
  • For a node the difference between height of left subtree and right subtree is not more than 1.

One approach to check balance condition for a node is by calculating height of left and right subtree and satisy the 3rd condition,then traverse down the tree to check for each child and keep continuing till you reach the leaf node. If condition is not satisfied for a node return false;

public class IsTreeBalance {


public boolean isBalance(TreeNode root){


if(root == null)

return true;

if (Math.abs(height(root.left)-height(root.right)) >1)

return false;

return isBalance(root.left) && isBalance(root.right);



}

  public int height(TreeNode node){


    if (node == null)

       return 0;
 
    return 1 + Math.max(height(node.left), height(node.right));

  }
}

So far so good. But the problem with this approach is that we visit each node (except root) more than once and hence not the best approach doing top-down check.

Opposite of top-down is bottom-up which is more efficient in this case. We start with leaf node and traverse up the tree. This way a node is visited only once.

public int isBalance1(TreeNode root){

if(root == null)

return 0;

int leftHeight = isBalance1(root.left);

int rightHeight = isBalance1(root.right);

if(Math.abs(leftHeight- rightHeight) > 1)

return -1;

return 1+Math.max(leftHeight, rightHeight);

&nbsp;

}
<pre>

Error while running junit with Spring 3.2


My first attempt of upgrading project to use spring 3.2.0.RELEASE.

I was trying to run bunch of Junit test cases (which run fine with 2.5.6 ) , i got following error


java.lang.NoSuchFieldError: NULL
at org.springframework.beans.factory.support.AbstractAutowireCapableBeanFactory.doCreateBean(AbstractAutowireCapableBeanFactory.java:532)
at org.springframework.beans.factory.support.AbstractAutowireCapableBeanFactory.createBean(AbstractAutowireCapableBeanFactory.java:461)
at org.springframework.beans.factory.support.AbstractBeanFactory$1.getObject(AbstractBeanFactory.java:295)
at org.springframework.beans.factory.support.DefaultSingletonBeanRegistry.getSingleton(DefaultSingletonBeanRegistry.java:223)
at org.springframework.beans.factory.support.AbstractBeanFactory.doGetBean(AbstractBeanFactory.java:292)
at org.springframework.beans.factory.support.AbstractBeanFactory.getBean(AbstractBeanFactory.java:194)

 

After searching google couple of suggestions people suggested

Spring 3.2 may not be compatible with old version of spring, so make sure about it.
Junit should be 4.5 + . I changed to 4.10
It didnt work then I found the class “TypeValue” is part of spring-expression jar file. So i added it explicitly with version 3.2 and it worked .

Happy Coding !!

Format Json String using JsonSerializer.


At times it is required to format the values while creating the json for eg Date, numeric value. The jackson json library provide a class JsonSerializer which helps in formatting the Object value.

For e.g
Convert the date return from DB in MM-dd-yyyy

class Person{

private String name;
private String city;
private Date DOB;

	public String getName() {
		return name;
	}
	public void setName(String name) {
		this.name = name;
	}
	public String getCity() {
		return city;
	}
	public void setCity(String city) {
		this.city = city;
	}
	public Date getDOB() {
		return DOB;
	}
        @JsonSerialize(using = JsonDateSerializer.class)
	public void setDOB(Date dOB) {
		DOB = dOB;
	}
}

public class JsonDateSerializer extends JsonSerializer {
	public void serialize(Object value, JsonGenerator gen, SerializerProvider arg2) throws IOException, JsonProcessingException {

	SimpleDateFormat formatter =
           new SimpleDateFormat("MM-dd-yyyy");
	String formattedDate = formatter.format(value);

	gen.writeString(formattedDate);

	}
}