Leetcode: Validate Binary Search Tree

Validate Binary Search Tree | LeetCode OJ

The inorder traversal of a binary search tree should be a sorted array. We can solve this problem using this concept. To know more about how inorder traversal is obtained please visit the corresponding blog post.

1. Get the inorder traversal of the given BST as a list
2. Iterate through the list and check if it is sorted

Remarks:

1. O(n) time complexity, n units for getting the inorder traversal and another n units for checking if the order is sorted
2. O(n) space complexity, for storing the inorder traversal output

# 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
        """
        inorder = self.inorderTraversal(root)
        for i in range(1, len(inorder)):
            if inorder[i - 1] >= inorder[i]:
                return False
        return True
    def inorderTraversal(self, root):
        return self.inorderTraversal(root.left) + [root.val] + self.inorderTraversal(root.right) if root else []