98. Validate Binary Search Tree

recursion solution
# 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
        """
        return self.isValidBSTRecur(root,float('-inf'),float('inf'))
    def isValidBSTRecur(self,cur,low,high):
        if cur is None:return True
        return cur.val>low and cur.val<high \
        and self.isValidBSTRecur(cur.left,low,cur.val) \
        and self.isValidBSTRecur(cur.right,cur.val,high)
        

Morris Inorder Traversal
# 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
        """
        #Morris Inorder Traversal 
        prev,cur=None,root
        while cur:
            if cur.left:
                node=cur.left
                while node.right and node.right!=cur:
                    node=node.right
                if node.right==cur:
                    if prev and prev.val>=cur.val:
                        return False
                    node.right=None
                    prev=cur
                    cur=cur.right
                else: 
                    node.right=cur
                    cur=cur.left
            else:
                #if left tree is empty, compare prev with current node 
                if prev and prev.val>=cur.val:
                    return False
                #set prev to cur, cur trace back 
                prev=cur
                cur=cur.right
                
        return True