Shasoosh Posted November 4, 2009 Share Posted November 4, 2009 Can someone provide a simple way to accomplish that? Thanks Link to comment Share on other sites More sharing options...
0 gian Posted November 4, 2009 Share Posted November 4, 2009 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 More sharing options...
0 Shasoosh Posted November 4, 2009 Author Share Posted November 4, 2009 oops , I forgot to mention that i'm trying to find an iterative way (not recursive) Link to comment Share on other sites More sharing options...
0 Shasoosh Posted November 6, 2009 Author Share Posted November 6, 2009 bump Link to comment Share on other sites More sharing options...
Question
Shasoosh
Can someone provide a simple way to accomplish that?
Thanks
Link to comment
Share on other sites
3 answers to this question
Recommended Posts