Leetcode Validate Binary Search Tree using BFS and Iteration

Question

I am trying to solve leetcode problem to validate a BST using BFS, while it passes some test cases, I have a problem with a particular test case.

Test Case: 
[5,4,6,null,null,3,7]

stout:
TreeNode{val: 5, left: TreeNode{val: 4, left: None, right: None}, right: TreeNode{val: 6, left: TreeNode{val: 3, left: None, right: None}, right: TreeNode{val: 7, left: None, right: None}}}

Tree

        5
     /    \
    4      6
   / \    / \ 
None None 3  7

My code below returns True while it should be False. I have implemented this locally using binary search tree data structure to debug but cannot find the flaw in my logic. I understand that the all the nodes greater than the root should be on the right and all the nodes less than the root on the left. Therefore my condition:

current_node.left.val >= root.val

is used to check for that, but it seems to be not doing so. Please help me understand the logic error.

# Definition for a binary tree node.
# class TreeNode:
#     def __init__(self, val=0, left=None, right=None):
#         self.val = val
#         self.left = left
#         self.right = right

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

Answer 1

I understand that the all the nodes greater than the root should be on the right and all the nodes less than the root on the left. Therefore my condition current_node.left.val >= root.val

Your description of the constraint is correct, but the code does not do what you describe. Your code ensures that the immediate child obeys this constraint, but not "all the nodes".

So in the example tree:

        5
     /     \
    4       6
   / \     / \ 
None None 3   7

...your code ensures that 6 > 5 and (at a deeper level) that 3 < 6, but it does not ensure that 3 > 5 (which is not true, and is enough to reject the tree as BST). Note that the nodes with these values are not in a a parent-child relation, but still you need to check that.

There are two common ways to implement this more thorough check:

• Perform an inorder traversal and make sure the values are traversed in ascending order

• Perform a preorder traversal and pass a valid range (min/max) to the recursive call. Each call checks that the current node has a value within those two extreme values.

I'll leave it to you to implement it that way. There are many Q&A on this site with a correct solution.