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.
key might be -1, so the comparison pre==-1 is not always valid.
ReplyDeleteI 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"
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!
DeleteHi, 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.
ReplyDeleteThanks,
Hi, I've written the exact code but it gives WA coz of the same reason. How did you overcome this ? Please update
DeleteInstead of taking INT_MAX and INT_MIN, you can take LONG_MAX and LONG_MIN.
Delete