I am looking at LeetCode problem 98. Validate Binary Search Tree:

Given the root of a binary tree, determine if it is a valid binary search tree (BST).

A valid BST is defined as follows:

• The left subtree of a node contains only nodes with keys less than the node's key.
• The right subtree of a node contains only nodes with keys greater than the node's key.
• Both the left and right subtrees must also be binary search trees.

What is the problem with the below provided code for validating the binary tree property with preorder traversal?

# Definition for a binary tree node.
# class TreeNode(object):
#     def __init__(self, val=0, left=None, right=None):
#         self.val = val
#         self.left = left
#         self.right = right
class Solution(object):
    def isValidBST(self, root):
        """
        :type root: TreeNode
        :rtype: bool
        """
        def preorder(root):
        
            if root.left!=None:
                if root.left < root.val:
                    preorder(root.left)
                else:
                    return False
            
        
            if root.right!=None:
                if root.right>root.val:
                    preorder(root.right)
                else:
                    return False
       
    t= preorder(root)
    return t!=False

It is returning False for the Test case where root=[2,1,3]

CodePudding user response：

You need to traverse the right-sub-tree only when the left-sub-tree is a valid one.

       def preorder(root):
            if root.left!=None:
                if root.left < root.val:
                    preorder(root.left)
                else:
                    return False
            
        
            if root.right!=None (and left-sub-tree is valid):
                if root.right>root.val:
                    preorder(root.right)
                else:
                    return False

Note: I don't know Python. Understand the comment while checking right-sub-tree.

CodePudding user response：

Several issues:

• root.left < root.val is comparing a node with an integer. This should be root.left.val < root.val. Same for the right side check.

• Although preorder returns False when there is a violation, the caller that makes the recursive call ignores this return value and happily continues. This is wrong. It should stop the traversal when the recursive call returns False, and itself return False to its caller.

• Not the main issue, but as preorder returns False, it should better return True in the remaining cases, so you can be sure that preorder returns a boolean, and don't have to treat None or compare the return value explicitly with False.

• The algorithm only checks whether a direct child of a node has a value that is not conflicting with the value of the parent, but that is not enough for validating a BST. All the values in the left subtree must be less than parent's value, not just the left child. So even if the above problems are fixed, this algorithm will wrongly say this BST is valid:

    4
   /
  1
   \
    9  <-- violation  (because of 4)
  

To solve the last point, you need to revise the algorithm: realise that when you are deep in a BST, there is a window of values that a subtree in a valid BST can have: there is a lower limit and an upper limit. In the above example the right child of the node 1 could only have a value in the range (1, 4).

Here is an implementation as a spoiler:

class Solution(object): def isValidBST(self, root): def preorder(root, low, high): return not root or ( low < root.val < high and preorder(root.left, low, root.val) and preorder(root.right, root.val, high) ) return preorder(root, -float("inf"), float("inf"))