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

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>