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 /**
02  * Definition for binary tree
03  * struct TreeNode {
04  *     int val;
05  *     TreeNode *left;
06  *     TreeNode *right;
07  *     TreeNode(int x) : val(x), left(NULL), right(NULL) {}
08  * };
09  */
10  bool isValidBSTHelper(TreeNode* root, int& prv)
11  {
12      if(root==NULL)
13         return true;
14      bool left=isValidBSTHelper(root->left,prv);
15      if((!left)||(prv>=root->val))
16         return false;
17      prv=root->val;
18      return isValidBSTHelper(root->right,prv);
19  }
20 class Solution {
21 public:
22     bool isValidBST(TreeNode *root) {
23         // Start typing your C/C++ solution below
24         // DO NOT write int main() function
25         int prv=INT_MIN;
26         return isValidBSTHelper(root,prv);
27     }
28 };
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