At first, I validate the tree directly based on the definition of a BST (each node is bigger than its left sub-tree and smaller than its right sub-tree). So I just traverse the tree and check every node.

```
# 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 isValidBST(self, root):
"""
:type root: TreeNode
:rtype: bool
"""
def check(r, val, left):
if r == None:
return True
if left and r.val >= val:
return False
elif not left and r.val <= val:
return False
return check(r.left, val, left) and check(r.right, val, left)
def traverse(r):
if r == None: return True
if not (check(r.left, r.val, True) and check(r.right, r.val, False)): return False
return traverse(r.left) and traverse(r.right)
return traverse(root)
```

Actually, we can also validate the condition that each node is larger than previously visited node. So we can apply inorder traversal while recording a 'pre' node. Following is a recursive implementation.

```
class Solution(object):
def isValidBST(self, root):
"""
:type root: TreeNode
:rtype: bool
"""
self.pre = ListNode(-2**32)
def inorder(r):
if r == None:
return True
a = inorder(r.left)
if r.val <= self.pre.val:
return False
self.pre = r
b = inorder(r.right)
return a and b
return inorder(root)
```

And this is a iterative implementation.

```
class Solution(object):
def isValidBST(self, root):
"""
:type root: TreeNode
:rtype: bool
"""
pre = ListNode(-2**32)
node, stack = root, []
while node!=None or stack:
while node != None:
stack.append(node)
node = node.left
node = stack.pop()
if node.val <= pre.val:
return False
pre = node
node = node.right
return True
```