Question: How to verify whether a binary tree is a binary search tree?
http://leetcode.com/2010/09/determine-if-binary-tree-is-binary.html
BST In-order with min and max pair
BST with Pre-order value.
http://www.geeksforgeeks.org/a-program-to-check-if-a-binary-tree-is-bst-or-not/
Read full article from Coding Interview Questions: No. 31 - Binary Search Tree Verification
http://leetcode.com/2010/09/determine-if-binary-tree-is-binary.html
BST In-order with min and max pair
BST with Pre-order value.
bool isBSTInOrderHelper(BinaryTree *p, int& prev) {
if (!p) return true;
if (isBSTInOrderHelper(p->left, prev)) {
if (p->data > prev) {
prev = p->data;
return isBSTInOrderHelper(p->right, prev);
} else {
return false;
}
}
else {
return false;
}
}
Solution 2: Increasing in-order traversal sequence
bool isBST_Solution2(BinaryTreeNode* pRoot)
{
int prev = numeric_limits<int>::min();
return isBSTCore_Solution2(pRoot, prev);
}
bool isBSTCore_Solution2(BinaryTreeNode* pRoot, int& prev)
{
if(pRoot == NULL)
return true;
return isBSTCore_Solution2(pRoot->pLeft, prev) // previous node
&& (pRoot->nValue >= prev) // current node
&& isBSTCore_Solution2(pRoot->pRight, prev = pRoot->nValue); // next node
}
The argument prev of the function isBSTCore_Solution2 above is the value of the previously visited node in pre_order traversal.
Solution 1: Verify value range of each node
bool isBST_Solution1(BinaryTreeNode* pRoot)
{
int min = numeric_limits<int>::min();
int max = numeric_limits<int>::max();
return isBSTCore_Solution1(pRoot, min, max);
}
bool isBSTCore_Solution1(BinaryTreeNode* pRoot, int min, int max)
{
if(pRoot == NULL)
return true;
if(pRoot->nValue < min || pRoot->nValue > max)
return false;
return isBSTCore_Solution1(pRoot->pLeft, min, pRoot->nValue)
&& isBSTCore_Solution1(pRoot->pRight, pRoot->nValue, max);
}
2
3
4
5
6
7
8
9
10
11
12
13
|
bool isBSTHelper(BinaryTree *p, int low, int high) {
if (!p) return true;
if (low < p->data && p->data < high)
return isBSTHelper(p->left, low, p->data) &&
isBSTHelper(p->right, p->data, high);
else
return false;
}
bool isBST(BinaryTree *root) {
// INT_MIN and INT_MAX are defined in C++'s <climits> library
return isBSTHelper(root, INT_MIN, INT_MAX);
}
|
bool isBST(struct node* root){ static struct node *prev = NULL; // traverse the tree in inorder fashion and keep track of prev node if (root) { if (!isBST(root->left)) return false; // Allows only distinct valued nodes if (prev != NULL && root->data <= prev->data) return false; prev = root; return isBST(root->right); } return true;}int isBST(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) { /* an empty tree is BST */ if (node==NULL) return 1; /* false if this node violates the min/max constraint */ if (node->data < min || node->data > max) return 0; /* otherwise check the subtrees recursively, tightening the min or max constraint */ return isBSTUtil(node->left, min, node->data-1) && // Allow only distinct values isBSTUtil(node->right, node->data+1, max); // Allow only distinct values} 