Reputation:
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
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
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