Find if a binary tree is a binary search tree

© Parineeth M R

Question 16. Find if a binary tree is a binary search tree


The initial approach that comes to mind is to check if the left child node is smaller than the parent node and the right child node is greater than the parent node for all the nodes in the tree. However this solution will not work as shown in the binary tree above. Every node satisfies the condition that the left child is smaller than the parent and the right child is greater than the parent. But the tree is still not a binary search tree since node 9 is incorrect. To correctly find out if a tree is a binary search tree, we should traverse the tree in-order and check if the nodes are present in ascending order

C/C++


/*cur_node: current node whose left and right sub-trees need to be checked
prev_node_pp: the in-order predecessor of cur_node
Return value: 1 if the tree is a binary search tree, 0 otherwise
*/
int is_bst(struct node *cur_node, struct node ** prev_node_pp)
{
	if (!cur_node)
		return 1;

	/*Check if the left sub-tree is a BST*/
	if (!is_bst(cur_node->left, prev_node_pp)) 
		return 0;

	/*If data in cur_node is <= to previous node then it is not a BST*/
	if (*prev_node_pp && cur_node->data <= (*prev_node_pp)->data)
		return 0;

	/*Update previous node to current node*/
	*prev_node_pp = cur_node;

	/*Check if the right sub-tree is a BST*/
	return is_bst(cur_node->right, prev_node_pp); 
}



Java


/*curNode: current node 
prevNodeArray: in-order predecessor of curNode is present in prevNodeArray[0]
Return value: true if the tree is a binary search tree, false otherwise
*/
public static boolean isBst(TreeNode curNode, TreeNode[] prevNodeArray)  {
	if (curNode == null)
		return true;

	/*Check if the left sub-tree is a BST*/
	if (!isBst(curNode.left, prevNodeArray)) 
		return false;

	/*If data in curNode is <= previous node then it is not a BST*/
	TreeNode prevNode = prevNodeArray[0];
	if (prevNode != null && curNode.data <= prevNode.data)
		return false;

	/*Update previous node to current node*/
	prevNodeArray[0] = curNode;

	/*Check if the right sub-tree is a BST*/
	return isBst(curNode.right, prevNodeArray); 
} 



Python


#cur_node: current node 
#prev_node_list: prev_node_list[0] has in-order predecessor of cur_node 
#Return values: True if the tree is a binary search tree, False otherwise
@staticmethod
def is_bst(cur_node, prev_node_list):
	if (not cur_node):
		return True

	#Check if the left sub-tree is a BST
	if (not TreeNode.is_bst(cur_node.left, prev_node_list)): 
		return False

	#If data in cur_node is <= previous node then it is not a BST
	prev_node = prev_node_list[0]
	if (prev_node and cur_node.data <= prev_node.data):
		return False

	#Update previous node to current node
	prev_node_list[0] = cur_node

	#Check if the right sub-tree is a BST
	return TreeNode.is_bst(cur_node.right, prev_node_list)