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 max)
return false;
else
{
return this.Check(node.LeftTree, min, node.Info) && this.Check(node.RightTree, node.Info + 1, max);
}
}
Sharing ideas, Sharing experiences 