Is Binary Tree a Binary Search Tree?


2. Is tree BinarySearchTree?

Problem:

Given a binary tree, determine if it is a Binary Search Tree (BST) or not?

Definition:

What is BST?

BST is a binary tree in which value of root is always greater than the value of every node on it’s left and is less than or equal to the value of every node on it’s right.

Solution:

This implementation is done using C#.NET.

class BinaryTree
{
public BinaryTreeNode Root { get; set; }

public bool IsBinarySearchTree()
{
Console.WriteLine("Checking if Tree is BST or not:");

if (this.Root != null)
{
int value = 0;

return this.Check(this.Root, ref value);
}

return true;
}

private bool Check(BinaryTreeNode currentNode, ref int lastNodeValue)
{
bool isTreeBST = false, leftTreePresent, rightTreePrsent ;

leftTreePresent = currentNode.LeftTree == null ? false : true;
rightTreePrsent = currentNode.RightTree == null ? false : true;

if (leftTreePresent)
{
isTreeBST = this.Check(currentNode.LeftTree, ref lastNodeValue);
}
else
{
isTreeBST = true;
}

if (isTreeBST && currentNode.Info > lastNodeValue)
{
Console.WriteLine("Processing Node With Value:{0}", currentNode.Info);

lastNodeValue = currentNode.Info;

isTreeBST = true;
}
else
{
isTreeBST = false;
}

if (isTreeBST && rightTreePrsent)
{
isTreeBST = this.Check(currentNode.RightTree, ref lastNodeValue);
}

return isTreeBST;
}
}

class BinaryTreeNode
{
public BinaryTreeNode LeftTree { get; set; }
public BinaryTreeNode RightTree { get; set; }
public int Info { get; set; }
}

Problem with the above code is that if a tree has Duplicate Values, it will fail.

The approach could be then to pass the Range in terms of Minimum and the Maximum Value of a particular node. Since we are traversing down from Root and knowing the min and max value of a root, we can appropriately limit the range and pass on to Left and Right Trees.


private bool Check(BinaryTreeNode node, int min, int max)
{
if (node == null)
return true;

if (node.Info < min || node.Info > max)
return false;
else
{
return this.Check(node.LeftTree, min, node.Info) && this.Check(node.RightTree, node.Info + 1, max);
}
}

Advertisements

About Sunil Singhal

A human being whose dreams are tied to a Horse that will never tire
This entry was posted in Algorithms and tagged , , , , , , , , , , , , . Bookmark the permalink.

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s