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:
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:
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)
It doesn't work because it doesn't check for duplicates or if leafs are actually in order. Thanks for the elegant solution!