what is wrong with my binary search tree validation code?

Question

According to the definition, a Binary Tree must satisfy the following conditions:
1. The left subtree of a node contains only nodes with keys less than the the node's key.
2. The right subtree of a node contains only nodes with keys greater than the node's key.
3. Both the left and right subtrees must also be binary search trees.

My code is returning True for the input [10 ,5, 15, #, #, 6, 20] but it's incorrect, it must return False.
The input follows a level order traversal, where '#' signifies a path terminator where no node exists below.

Here is the tree:

Here is my code :

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


    def isValidBST(self, root)
    """  
    :type root: TreeNode  
    :rtype: bool  
    """  

    if not root:  
        return True  
    else:  
        if root.left and root.right:  
            return root.left.val < root.val < root.right.val and \    
                   self.isValidBST(root.left) and self.isValidBST(root.right)  
        elif root.left and not root.right:  
            return root.left.val < root.val and self.isValidBST(root.left)  
        elif root.right and not root.left:  
            return root.right.val > root.val and self.isValidBST(root.right) 
        else:  
            return True

Could you show what the tree is you are having an issue with in some other manner? For example, (val left-subtree right-subtree)? — Scott Hunter

Scott Hunter Scott Hunter · Accepted Answer · 2015-08-21T14:05:52

Consider a BST where A is the root value, B is the value at the root of its left subtree, and C is the value at the root of the right subtree under that. Your code will verify that A > B, and that B < C. But it does not check to see if A > C.

Or, from your example: It checks that 5<10, 10<15, 6<15, and 15<20, but does not check that 6>10.

Recall that the definition of a BST talks about all nodes in a subtree, not just the root.

what is wrong with my binary search tree validation code?

2 Answers