6
\$\begingroup\$

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?

\$\endgroup\$
4
\$\begingroup\$

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)
\$\endgroup\$
1
\$\begingroup\$

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.

\$\endgroup\$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.