leetcode Question 122: Validate Binary Search Tree

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.
Example 1:
2
/ \
1 3
Binary tree [2,1,3], return true.
Example 2:
1
/ \
2 3
Binary tree [1,2,3], return false.

Analysis:

The simplest is way of this problem is to utilize the property of the BST, of which the inorder traversal is sorted by ascending order. We could just save the inorder results into one vector, and a check will solve the problem.

A slight more efficient soluiton is to save the previous node in our recursion, by simply checking the currnt node with previous node in each traversal, we could find if the tree is a BST or not.

Code(C++):

/**
* Definition for a binary tree node.
* struct TreeNode {
* int val;
* TreeNode *left;
* TreeNode *right;
* TreeNode(int x) : val(x), left(NULL), right(NULL) {}
* };
*/
class Solution {
public:
void inorder(TreeNode* root, TreeNode* &prev, bool &res){
if (!root || !res) {return;}
inorder(root->left, prev, res);
if (prev && root->val <= prev->val ){
res = false;
return;
}
prev = root;
inorder(root->right,prev, res);
}
bool isValidBST(TreeNode* root) {
bool res = true;
TreeNode* prev = NULL;
inorder(root, prev, res);
return res;
}
};

Code (Python):

# Definition for a binary tree node.
# class TreeNode(object):
# def __init__(self, x):
# self.val = x
# self.left = None
# self.right = None
class Solution(object):
def inorder(self, root, prev, res):
if not root or not res:
return
self.inorder(root.left, prev, res)
if prev[0] and root.val <= prev[0].val:
res[0] = False
return
prev[0] = root
self.inorder(root.right, prev, res)
def isValidBST(self, root):
"""
:type root: TreeNode
:rtype: bool
"""
prev = [None]
res = [True]
self.inorder(root, prev, res)
return res[0]

5 comments:

  1. key might be -1, so the comparison pre==-1 is not always valid.

    I like your code in post "leetcode Question 75: Recover Binary Search Tree".
    In that post, you use a pointer to store last traversed node, and it naturally enables checking NULL to know whether there is a previous one. It's a great idea.

    Or use another flag to show whether there is a previous node, like "bool started"

    ReplyDelete
    Replies
    1. Hi there, thanks for pointing out the mistake. I have made the modification, I think usually just set the pre = INT_MIN would prevent most cases for the input. Please check the new code in the post. Thanks a lot!

      Delete
  2. Hi, your new C++ code may cause wrong answer error. Because, the tree may contain only one root node whose value might be INT_MAX or INT_MIN, which is a valid BST while in your code, it'll return false.

    Thanks,

    ReplyDelete
    Replies
    1. Hi, I've written the exact code but it gives WA coz of the same reason. How did you overcome this ? Please update

      Delete
    2. Instead of taking INT_MAX and INT_MIN, you can take LONG_MAX and LONG_MIN.

      Delete