Question:
Published on: 21 January, 2022

"Write an algorithm to test whether a given binary tree is a binary search tree."

Answer:

A binary search tree (BST) is a node based binary tree data structure which has 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

/* Returns true if a binary tree is a binary search tree */

int isBST(struct node* node) {

  if (node == NULL)

    return(true);



  /* false if the max of the left is > than us */

  if (node->left!=NULL && maxValue(node->left) > node->data)

    return(false);



  /* false if the min of the right is <= than us */

  if (node->right!=NULL && minValue(node->right) < node->data)

    return(false);



  /* false if, recursively, the left or right is not a BST */

  if (!isBST(node->left) || !isBST(node->right))

    return(false);



  /* passing all that, it's a BST */

  return(true);

}

Subjects
Trending

What is tree traversal?

View : 25
23 January, 2022

Random questions