I think one of reasons that this question is on the verge of getting closed, is that the code presented doesn't make much sense combined with a question of iterative version. But let us come to back that.
Code and style review
- Good naming of methods and variables – You are trying to follow the PEP8 and that is good
- Combine similar
if statements – When you have similar
if condition, and they do the same, then combine them using the
\ (line continuation) or parenthesis to break long if conditions – This is a matter of personal preferences, and one area where I'm not sure what I prefer to do in all cases. But if you have a long
if condition, you can either break it using a single
\ at the end of the line, or add the otherwise unneccessary parenthesis around the entire condition.
- Add vertical space between non-similar
if statements – In some places it can be good to introduce a little vertical space. This is especially true with following
else blocks. If not vertically spaced, one might wonder if they should have been using
else instead. And if they really are meant to be separate
if statements, then separate them using extra newlines. This enhance readability, and code understanding
None conditions – Consider whether you want to test directly on
not node or if you want to use the more verbose
node is None. In most cases they are identical, but I tend to prefer the
not node version my self.
Bug: Not keeping the
key_max whilst traversing tree – Your code sets these to
None, which would introduce errors if you have a tree with a little more levels then your test case, and you first traverse a left tree, and then go down the right tree. That value could now be higher than the root value, and you'll be happy with that. So extend test cases, and then afterwards correct the bug.
With these options implemented you'll get the following (untested) code:
def is_bst(node, key_min=None, key_max=None):
"""Checks is the subtree rooted at this node is a BST."""
if node is None:
if (not key_max and node.key >= key_max) \
or (not key_min and node.key <= key_min):
return is_bst(node.left, key_min, node.key) \
and is_bst(node.right, node.key, key_max)
Your implementation is good, and should do what it is supposed, with correction of bug, and does so in a recursive manner. You can't do it entirely iterative as retrieving the values of a tree is not an iterative procedure.
However, you do have the option of creating/returning/yielding something which you can use in an iterative manner. Either iterating over your returned list from
inorder(), or by implementing an iterative version of the traversal, as I've done in my answer for
If having some you can iterate over you could do either of the following variants:
# First variant: Manually keeping the previous_node
previous_node = None
for node in inorder(root):
if previous_node and previous_node.key > node.key:
previous_node = node
# Second variant: Using the itertools.pairwise iterator
return any(prev.key > node.key for prev, node in pairwise(inorder(root)))
The last one depending on the itertools.pairwise recipe, which returns all pairs of nodes from the start through end.
Do however note, that neither of these methods are tested for efficiency or speed, but are mostly presented as alternate methods on how to do the check whether all the values are in sorted order which seems to the criteria for a binary search tree.