Verifying whether a tree is bst or not Python -

Verifying whether a tree is bst or not Python -

i have practice interview question tells me verify if tree balanced search tree or not , give verification method... have class as

class node: def __init__(self, k, val): self.key = k self.value = val self.left = none self.right = none

and other function definitions tree max , min values as

def tree_max(node): maxleft = float('-inf') if not node.left else tree_max(node.left) maxright = float('-inf') if not node.right else tree_max(node.right) homecoming max(node.value, maxleft, maxright) def tree_min(node): minleft = float('-inf') if not node.right else tree_min(node.left) minright = float('-inf') if not node.left else tree_min(node.right) homecoming min(node.value, minleft, minright)

my verification method as

def verify(node): if tree_max(node.left) <= node.value , node.value <= tree_min(node.right): if verify(node.left) , verify(node.right): homecoming true else: homecoming false else: homecoming false

my problem occurs when seek implement verification method seem false when seek create bst tree. implementation follows:

root= node(10, "hello") root.left = node(15, "fifteen") root.right= node(30, "thirty") print verify(root) root = node(10, "ten") root.right = node(20, "twenty") root.left = node(5, "five") root.left.right = node(15, "fifteen") print verify(root)

both giving me false...is there problem verification function or min/max function...any help appreciated.

i see 4 errors in code.

first, check null children backwards in tree_min. is, you're checking if node.right exists before accessing node.left, , vise versa.

second, tree.min returns negative infinity when called on leaf node. need utilize positive infinity in min calculation (negative infinity right in max version).

third, have logic error within verify, unconditionally calls tree_min or tree_max , on it's kid nodes, if 1 or both of them none. suggest making functions handle beingness passed none, rather relying on caller right thing. simplifies min , max code bit!

lastly, you're doing comparisons on node.value, string you're giving each node. suspect want comparing using node.key instead. comparing float (like float("-inf")) string (like "ten") error in python 3, , in python 2 legal, doesn't work expect.

with issues fixed, expected results when create valid , invalid trees. 2 examples both invalid though, if using them test, false result.

finally, couple of minor style issues (that aren't bugs, still things improved). python supports chained comparisons, can simplify first if statement in verify tree_max(node.left) <= node.key <= tree_min(node.right). can farther simplify part of code connecting checks and rather nesting additional if statement.

here's version of code works me (using python 3, though think backwards compatible python 2):

class node: def __init__(self, k, val): self.key = k self.value = val self.left = none self.right = none def tree_max(node): if not node: homecoming float("-inf") maxleft = tree_max(node.left) maxright = tree_max(node.right) homecoming max(node.key, maxleft, maxright) def tree_min(node): if not node: homecoming float("inf") minleft = tree_min(node.left) minright = tree_min(node.right) homecoming min(node.key, minleft, minright) def verify(node): if not node: homecoming true if (tree_max(node.left) <= node.key <= tree_min(node.right) , verify(node.left) , verify(node.right)): homecoming true else: homecoming false root= node(10, "hello") root.left = node(5, "five") root.right= node(30, "thirty") print(verify(root)) # prints true, since tree valid root = node(10, "ten") root.right = node(20, "twenty") root.left = node(5, "five") root.left.right = node(15, "fifteen") print(verify(root)) # prints false, since 15 left of 10

python binary-search-tree