I have looked at this code line by line maybe 100 times and I am stumped. Why doesn't this work????

Problem: input of [5,4,6,null,null,3,7] (this is a BST with 5 being the root and 4 and 6 being its left and right nodes) returns True when it should return False (3 should be not be to the right of parent node 5). False should be returned at the first nested if statement in the while loop.

def isValidBST(self, root: Optional[TreeNode]) -> bool:
    if not root:
        return True
    # BFS method
    current_node = root
    queue = []
    queue.append(current_node)
    
    while len(queue) > 0:
        current_node = queue.pop(0)
        if current_node.left:
            if (current_node.val > current_node.left.val) and (root.val > current_node.left.val):
                queue.append(current_node.left)
            else:
                return False
        if current_node.right:
            if (current_node.val < current_node.right.val) and (root.val < current_node.right.val):
                queue.append(current_node.right)
            else:
                return False
    return True

CodePudding user response：

The tree for which your code fails is:

          5
        /   \
       4     6
            / \
           3   7

When current_node is 6, your code checks that root.val > current_node.left.val, which means it checks that 5 > 3. This is true. And so it wrongly concludes there is no problem there, yet there is.

You may now think to just change the direction of that comparison, but there is a logical error in your approach: it is not enough to compare the root with every node in its subtree. For instance, in the following tree you should detect that 3 is violating the BST property, even though it is not in conflict with the root:

              2
               \
                5
                 \
                  6
                 /
                3

The conflict is with the value 5, which is neither the parent of 3, nor the root.

In conclusion, a BFS traversal is not really an ideal tool to verify a BST. Although it surely can be done, it is more natural to use DFS, as it allows to carry down the (accumulated) limitations that will apply to every node in the subtree.