Check If tree is a Binary Search Tree

Hi , this post is to find if tree is the binary search tree or not.

Common approach

Check for each root , right child should be large , and left child should be small.

but , this is not a correct approach.

It can show wrong result , for more understanding read from the URL given below.

Correct Approach

1. Perform a In order Traversal of a given tree and store the result in the array.

Code Snippet:

Create ArrayList arrayList

InorderTraversal(Node n){

if(n != null){

InorderTraversal(n.leftChild);

arrayList.add(n.value);

InorderTraversal(n.rightChild);

}

}

}

2.Now check the array show be in ascending order, if it is not in ascending order than the tree it is  not a Binary search Tree.

Now we have and arrayList we can perform the following action to get the final result.

code Snippet

boolean checkArrayList(ArrayList arrayList){

for(int i=0;i<arrayList-1;i++){

if(arrayList[i]>arrayList[i+1])

return false;

}

return true;

}

This method will return true or false.

More info on binary Search Tree.

http://en.wikipedia.org/wiki/Binary_search_tree

More info on Code Snippets

http://www.geeksforgeeks.org/a-program-to-check-if-a-binary-tree-is-bst-or-not/

Visual Tutorial

http://www.youtube.com/watch?v=aNtDir94pcA

Advertisements