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.
• A single node tree is a BST

it's easy to make it wrong by just checking one level of validity.

Borrowed ideas from http://www.lifeincode.net/programming/leetcode-validate-binary-search-tree-java/

The algorithm I take is the third one:

The in-order traverse can helps us. Doing a in-order traverse on a BST, the output will be a increasing sequence. We do in-order traversal and keep checking if they are in increasing order.

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39

public class Solution { /** * @param root: The root of binary tree. * @return: True if the binary tree is BST, or false */ public boolean isValidBST(TreeNode root) { // write your code here /* return isValidBST(root, Integer.MAX_VALUE, Integer.MIN_VALUE); } public boolean isValidBST(TreeNode root, int max, int min) { if (root == null) return true; if (root.val <= min || root.val >= max) return false; return isValidBST(root.left, Math.min(max, root.val), min) && isValidBST(root.right, max, Math.max(min, root.val)); }*/ return inorderTraverse(root); } TreeNode prev = null;//key: prev is previous root shared by both left and right //it does not change for all subtrees   public boolean inorderTraverse(TreeNode root) { if (root == null) return true; if (!inorderTraverse(root.left)) return false; if (prev != null) { if (root.val <= prev.val) return false; } prev = root;//in order if (!inorderTraverse(root.right)) return false; return true; } }