user6163598
user6163598

Reputation:

Determine if BST

class BTNode:
    """Binary Tree node."""
    def __init__(self: ’BTNode’, data: object,
                 left: ’BTNode’=None, right: ’BTNode’=None) -> None:
      """Create BT node with data and children left and right."""
      self.data, self.left, self.right = data, left, right

 def is_bst(t: BTNode) -> bool:

   if not t:
     return False
   if not t.left and not t.right:
     return True
   if t.left and t.right:
     if not(t.data > t.left.data) or not(t.data < t.right.data):
       return False
   else:
     return is_bst(t.left) and is_bst(t.right)

Function description says return True iff binary tree rooted at t has the BST property.

is_bst(BTNode(8, BTNode(9, BTNode(2, None, None), BTNode(6, None, None)),\
BTNode(10, None, None)))

The following call returns True when it should return False since 9 which is in the left branch is greater than the root value 8. This violates BST property

I am not sure why I am getting this output. Can you please tell me what is wrong with my function.

Thank you

Upvotes: 0

Views: 312

Answers (2)

qwertyuip9
qwertyuip9

Reputation: 1632

To answer this:

I am not sure why I am getting this output.

The root node (8) is indeed less than its right child node (10) - which your fourth if statement is checking. As a result, the function returned True without doing any recursion for the tree that you provided.

  if t.right:
     if t.data < t.right.data:
        return True

To answer this:

Can you please tell me what is wrong with my function.

Similar to another answer, it'll be easier to check whether there is a fault in the tree by checking for opportunities to return False. I wrote this quickly (haven't tested it) but it will do a "pre-order" traversal of the tree with recursion.

if not t:
    return False

if t.left:
    if t.data > t.left.data:
        return is_bst(t.left)
    else:
        return False

if t.right:
    if t.data < t.right.data:
        return is_bst(t.right)
    else:
        return False

return True

Upvotes: 0

aghast
aghast

Reputation: 15310

Your logic is backwards.

For example, you check t.left, and return True. But in that case, you never check t.right.

When t.left check fails, you simply fall through to checking t.right, and possibly return true, ignoring the failure on t.left.

Instead, you should look for failures. Basically, every return you do should be a return False, and only if all the tests pass will you return true at the end.

if something wrong with t:
    return False
if something wrong with t.data:
    return False
if something wrong with t.left:
    return False
if something wrong with t.right:
    return False

# Apparently, nothing is wrong
return True

Upvotes: 0

Related Questions