Check whether a binary tree is a binary search tree
  • node
  • binarysearchtree
  • pointer
  • binarytree
  •   
  • Posted: 5 years ago
  • Edit
  • answers (1)
  • views (3887)

Write an algorithm to check whether whether a binary tree (pointer to its root) is a binary search tree?


Posted Answers

A binary search tree is a binary tree data having the following properties:


    The left subtree of a node contains only nodes with keys less than the node’s key.
    The right subtree of a node contains only nodes with keys greater than the node’s key.
    Both the left and right subtrees must also be binary search trees.

The algorithm is based on In-Order Traversal.

  • If the in-order traversal of the Binary Tree is sorted in ascending order then the tree is Binary Search Tree.
  • Else, it is not Binary Search Tree.

Time Complexity: \( O(n) \).



< Alternate Solution > (When space is a constraint) : Here, we traverse down the tree recursively from root and check whether the value at the current node is between the minimum and maximum value. When the left subtree is accessed we check the node value with the minimum one and for the right subtree with the maximum one.

public boolean isBinarySearchTree(Node root){

return isBinarySearchTree(root, Integer.MIN_VALUE, Integer.MAX_VALUE) );

}

public boolean isBinarySearchTree(Node node, int minimum, int maximum){

/* Empty tree is a BST */
if(node == null)
return true;
else{

/* Check the left subtree */
boolean left = isBinarySearchTree(node.left, minimum, node.data);

/* If the left subtree is not BST */
if (!left)
return false;

/* Check the right subtree */
boolean right = isBinarySearchTree(node.right, node.data+1, maximum);

return right;
}
}

You need to Sign In to post your solution.