CODEWITHSUNDEEP
pythonbinary-search-tree
anon anon
anon anon

Reputation: 161

Analyze code If A Binary Search Tree Is a Binary Search Tree

I was looking at code for if a Binary Tree is a BST, and I was confused at how it is doing the comparison. 

def is_bst(cur_node, prev_node_list):
    if (not cur_node):
        return True

    #Check if the left sub-tree is a BST
    if (not TreeNode.is_bst(cur_node.left, prev_node_list)): 
        return False

    #If data in cur_node is <= previous node then it is not a BST
    prev_node = prev_node_list[0]
    if (prev_node and cur_node.data <= prev_node.data):
        return False

    #Update previous node to current node
    prev_node_list[0] = cur_node

    #Check if the right sub-tree is a BST
    return TreeNode.is_bst(cur_node.right, prev_node_list)

I was wondering what 

if (prev_node and cur_node.data <= prev_node.data):
  return False

is doing. If the code is constantly checking the left subtrees, shouldn't the next value be less than the previous node?

Upvotes: 0

Views: 36

Answers (1)

drahnoel
drahnoel

Reputation: 227

The code visits all elements in sorted order. That is, first left nodes then current node than right node. If you replace the check with the previous node with a print statement, you get the elements from smallest to biggest (if the tree was valid).

Now, it is sufficient to check, if these vistited elements are sorted.

To answer your question: the current node is checked after the left node. The code first goes to the very left leaf node.

Upvotes: 1

Related Questions