CODEWITHSUNDEEP
pythontreebinarybinary-search-tree
Venkatesh Marepalli
Venkatesh Marepalli

Reputation: 606

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

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"

Upvotes: 0

Views: 217

Answers (1)

Shubham Bakshi
Shubham Bakshi

Reputation: 156

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.

Upvotes: 1

Related Questions