Problem with Python code checking if a given Binary Tree is BST

Question

To solve this problem I like the InOrderTraversal approach described here in method 4

The code doesnt work for the case where right child of the roots left child is greater than root node. Example:

        9
     5    10
   4  11    12

Can someone help me fix this? I noticed when I print prev.data it only prints 3 elements

class TreeNode:
    def __init__(self, data):
        self.data = data
        self.left = None
        self.right = None


def isBSTUtil(root, prev):
    if root!=None:
        if isBSTUtil(root.left,prev)==False:
            return False

        if prev!=None and prev.data>root.data:
            return False

        prev=root    
        return isBSTUtil(root.right,prev)
    return True

def isBST(root):
    prev = None
    return isBSTUtil1(root,prev)


if __name__ == "__main__":
    root = TreeNode(9)
    root.left = TreeNode(5)
    root.right  = TreeNode(10)
    root.left.left = TreeNode(4)
    root.left.right = TreeNode(11)
    root.right.right = TreeNode(12)    
    if isBST(root):
        print "is BST"
    else:
        print "Not a BST"

Shubham Bakshi · Accepted Answer · 2019-12-26 14:44:57Z

1

I am labeling the key statements to make explanation simpler.

class TreeNode:
    def __init__(self, data):
        self.data = data
        self.left = None
        self.right = None


def isBSTUtil(root, prev):
    if root!=None:          # statement 1
        if isBSTUtil(root.left,prev)==False:     # statement 2
            return False      # statement 3

        if prev!=None and prev.data>root.data:     #statement 4
            return False      # statement 5

        prev=root             # statement 6
        return isBSTUtil(root.right,prev)      # statement 7
    return True               # statement 8

def isBST(root):
    prev = None
    return isBSTUtil1(root,prev)


if __name__ == "__main__":
    root = TreeNode(9)
    root.left = TreeNode(5)
    root.right  = TreeNode(10)
    root.left.left = TreeNode(4)
    root.left.right = TreeNode(11)
    root.right.right = TreeNode(12)    
    if isBST(root):
        print "is BST"
    else:
        print "Not a BST"

Let's trace the solution with each function call

step 1: `isBST(root)` is called. Here root = 9
step 2: `isBSTUtil(root, prev)` is called. Here root = 9, prev = None
step 3: since root is not None, a recursive call is made to `isBSTUtil(root, prev)`. Now, root = 5 (left node of root 9), prev = None
step 4: again, since root is not None, another recursive call is made to isBSTUtil(root, prev) with root = 4, prev = None
step 5: root is not None here also, so one more recursive call is made to isBSTUtil(root, prev) with root = None (left of 4 is None), prev = None
step 6: Now at this step, the condition 'if root!=None' (statement 1) fails and the program return True (statement 8)
step 7: recursive call which was halted at step 4 resumes with statement 2 and this condition will fail as the return statement in step 6 was True
step 8: statement 4 starts execution. statement 4 fails as 'prev' is not None. with the execution of statement 6 (prev=root), prev now has the value = 4

Now, I am assuming you already have gotten the flow of local variables with each recursive call..I will skip other nodes and jump directly to node with value = 5

step 1: At this point, after all the recursive calls, root = 5, prev = 5 (after execution of statement 6) and now recursive call to the right subtree is being made (statement 7)
step 2: with this recursive call, now root = 11 (right child of 5) and prev = 5
step 3: Now at this step statement 4 will execute as prev is not None anymore and the second condition here (prev.data>root.data) will fail as prev.data = 5 and root.data=11 at this point. Hence the statement 5 will never execute and it won't return False. And this is main reason of faulty behavior. Ideally, at this point, the statement should have returned False, which would make the output of the program correct.

Now I am hoping that you have got the problem. You should keep a global copy of prev instead of passing it locally as mentioned in the geeksforgeeks website as well.

answered Dec 26, 2019 at 14:44

Shubham Bakshi

1567 bronze badges

Sign up to request clarification or add additional context in comments.

3 Comments

Venkatesh Marepalli Over a year ago

Thanks for your detailed explanation but if you see geeksforgeeks in Method 4 the second approach is what I used which is to avoid static variables by passing local variable. Do you think the python implementation over there is wrong?

Venkatesh Marepalli Over a year ago

Can you fix the code without using gloal variables and just using the local variables within the recursion?

Shubham Bakshi Over a year ago

@VenkateshMarepalli I would suggest using in order successor of each node instead of prev, while checking statement 4. For the above tree, the in order traversal will be 4 5 11 9 10 12.Now, the inorder successor of node 11 will be 9 and now the statement 4 will return True and final output should return False.

Collectives™ on Stack Overflow

Problem with Python code checking if a given Binary Tree is BST

1 Answer 1

3 Comments

Your Answer

Hot Network Questions

Collectives™ on Stack Overflow

1 Answer 1

3 Comments

Your Answer

Sign up or log in

Post as a guest

Related