Validate Binary Search Tree

Problem: Validate Binary Search Tree

The general idea is to produce in-order traversal of given tree and check the traversal whether previous element is smaller than latter one.

Code in Python:

class Solution(object):
    def isValidBST(self, root):
        """
        :type root: TreeNode
        :rtype: bool
        """
        if not root: return True

        inorder = []
        def dfs(node):
            if node.left: dfs(node.left)
            inorder.append(node.val)
            if node.right: dfs(node.right)
        dfs(root)

        for i in xrange(1, len(inorder)):
            if inorder[i-1] >= inorder[i]: return False
        return True