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

Random questions