You are viewing a single comment's thread. Return to all comments →
I like the approach with inorder traverse. But we have to check not only the order, but also that there are no duplicates. I used "set" for that:
list(set(my_list))
Here is my code:
def checkBST(root): list_ = [] def inorder(node): if node.data: if node.left: inorder(node.left) list_.append(node.data) if node.right: inorder(node.right) return list_ inorder_list = inorder(root) return sorted(list(set(inorder_list))) == inorder_list
Loved how you turned the list into a set to filter duplicates.
I first tried to check every node, but I couldn't figure out how to check the entire tree until I read your code, here's the code I tried first:
def checkBST(root): truth = True if(root.left != None): truth *= root.left.data < root.data truth *= checkBST(root.left) if(root.right != None): truth *= root.data < root.right.data truth *= checkBST(root.right) return(truth)
It doesn't work because it doesn't check for duplicates or if leafs are actually in order. Thanks for the elegant solution!
Trees: Is This a Binary Search Tree?
You are viewing a single comment's thread. Return to all comments →
I like the approach with inorder traverse. But we have to check not only the order, but also that there are no duplicates. I used "set" for that:
Here is my code:
Loved how you turned the list into a set to filter duplicates.
I first tried to check every node, but I couldn't figure out how to check the entire tree until I read your code, here's the code I tried first:
It doesn't work because it doesn't check for duplicates or if leafs are actually in order. Thanks for the elegant solution!