• 0

Pseudo-Code to check if a tree is a Binary search tree


Question

3 answers to this question

Recommended Posts

  • 0

Your goal is to actually check if you print out the tree, will it come out sorted?

That said here is a piece of code I like.

/*
 Returns true if the given tree is a binary search tree
 (efficient version).
*/
int isBST2(struct node* node) {
  return(isBSTUtil(node, INT_MIN, INT_MAX));
}

/*
 Returns true if the given tree is a BST and its
 values are >= min and <= max.
*/
int isBSTUtil(struct node* node, int min, int max) {
  if (node==NULL) return(true);

  // false if this node violates the min/max constraint
  if (node->data<min || node->data>max) return(false);

  // otherwise check the subtrees recursively,
  // tightening the min or max constraint
  return
	isBSTUtil(node->left, min, node->data) &&
	isBSTUtil(node->right, node->data+1, max)
  );
}

This is taken from Stanford's CS Library introduction to trees.

It's pretty simple, when you go down the left all you have to do is check if your current node is smaller than the parent node.

When you go down the right you have to check if the current node is larger than the parent node.

You only go through the tree once.

Link to comment
Share on other sites

This topic is now closed to further replies.
  • Recently Browsing   0 members

    • No registered users viewing this page.