Validate Binary Search Tree

Given a binary tree, determine if it is a valid binary search tree (BST).

Assume a BST is defined as follows:

  • 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.
C++:
01 const int MAX=2147483647;
02 const int MIN=-2147483648;
03 
04 bool isBST(TreeNode* root, int max, int min)
05 {
06     if(root==NULL)
07         return true;
08     int data=root->val;
09     if((data>=max)||(data<=min))
10         return false;
11     if(isBST(root->left,data,min)==false)
12         return false;
13     if(isBST(root->right,max,data)==false)
14         return false;
15     return true;
16 }
17 
18 bool isValidBST(TreeNode *root) {
19      return  isBST(root,MAX,MIN);
20 }
Advertisements
This entry was posted in Recursive, Tree. Bookmark the permalink.

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s