Python solution with detailed explanation


  • 0
    G

    Solution

    Validate Binary Search Tree https://leetcode.com/problems/validate-binary-search-tree/?tab=Description

    Algorithm

    • The intervals, m_min and m_max are inclusive intervals i.e. [m_min, m_max]. Therefore the condition:
      if root.val > m_max or root.val < m_min:
      return False
    • Since they are inclusive, we need the following - reduce root.val by 1 and add one to it.
    class Solution(object):
        def helper(self, root, m_min, m_max):
            if root == None:
                return True
            if root.val > m_max or root.val < m_min:
                return False
            return self.helper(root.left, m_min, root.val-1) and self.helper(root.right, root.val+1, m_max)
        
        def isValidBST(self, root):
            """
            :type root: TreeNode
            :rtype: bool
            """
            return self.helper(root, float('-inf'), float('inf'))
    

Log in to reply
 

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.