HackerRank Binary search tree validation

Question

From here:

def checkBST(root):
 prev_val = -1
 for node in in_order_sort(root):
 if node.data <= prev_val:
 return False
 prev_val = node.data
 return True
def in_order_sort(node):
 if node.left:
 yield from in_order_sort(node.left)
 yield node
 if node.right:
 yield from in_order_sort(node.right)

Looking for any suggestions on improving this. It's pretty concise.

The input data is constrained between \0ドル\$ and \10ドル^4\$ so I can "get away" with setting the initial value to -1. The input func name checkBST is also predefined.

It seems that short of knowing you can validate a binary tree via an in-order traversal this would get complicated, but knowing that makes it straightforward?

Answer 1

The prev_val handling is slightly clumsy. I would personally prefer using the pairwise() recipe from itertools. You could then replace the loop altogether with all(...), which more clearly expresses your intentions.

I would also prefer to see the generator yield node.data instead of yield node.

from itertools import tee
def checkBST(root):
 a_iter, b_iter = tee(in_order_traversal(root))
 next(b_iter, None)
 return all(a <= b for a, b in zip(a_iter, b_iter))
def in_order_traversal(node):
 if node.left:
 yield from in_order_sort(node.left)
 yield node.data
 if node.right:
 yield from in_order_sort(node.right)

Answer 2

I'd leverage python's builtin functions by flattening the tree to a list, then checking if it's sorted in ascended order and whether it has any duplicates:

def checkBST(root):
 flat = flatten(root)
 return flat == sorted(flat) and len(flat) == len(set(flat))
def flatten(tree):
 if tree:
 return flatten(tree.left) + [tree.data] + flatten(tree.right)
 else:
 return []

This will almost certainly be slower though.