# Use generator to do inorder traversal

I am not used to generators and wonder how to make code cleaner/Pythonic in the generator part.

The function is about validating a binary search tree. The inorder_gen function yield one element a time. The main function compares the value yielded and previous yielded value to determine whether BST's invariant is violated.

# Definition for a binary tree node.
# class TreeNode(object):
#     def __init__(self, x):
#         self.val = x
#         self.left = None
#         self.right = None

class Solution(object):

def isValidBST(self, root):
"""
:type root: TreeNode
:rtype: bool
"""
last_val = None
for idx, v in enumerate(self.inorder_gen(root)):
if idx != 0 and v <= last_val:
return False
last_val = v
return True

def inorder_gen(self, node):
if node is None:
return
if node.left != None:
for v in self.inorder_gen(node.left):
yield v
yield node.val
if node.right != None:
for v in self.inorder_gen(node.right):
yield v


## 1 Answer

Your structure seems adequate, but there are a couple of mistakes, and some new language syntax in 3.3 that will make things even clearer:

1. That name!

def inorder_gen(self, node):


The name does make it obvious what order you're using. And it also explains that you're writing a generator - which is putting implementation details in the public interface. Don't do that. You could go with inorder(), but even better would be to make your class iterable using the standard Python approach. See this SO answer for an example of how.

2. You were off to a good start ...

if node is None:
return
if node.left != None:


... but then you tried to use != None. Use is None or is not None instead. (Like you did on the first line!)

3. Use Python's yield from expression to connect a nested generator to your caller. This code:

if node.left != None:
for v in self.inorder_gen(node.left):
yield v
yield node.val
if node.right != None:
for v in self.inorder_gen(node.right):
yield v


Becomes this:

yield from self.inorder_gen(node.left) if node.left is not None else ()
yield node.val
yield from self.inorder_gen(node.right) if node.right is not None else ()


And if your nodes default to truthy (which most objects do), you can replace if node.left is not None with if node.left, for more readability!

yield from self.inorder_gen(node.left) if node.left else ()
yield node.val
yield from self.inorder_gen(node.right) if node.right else ()

4. Bonus: If you make your TreeNode class iterable, as mentioned in #1, and you use yield from as mentioned in #3, you can make your code even smaller! Since the nodes are iterable, and since yield from will accept an iterable, you can yield from the nodes directly, like this:

# NOTE: This has to be on the node class, so if you can't change
# that, it won't work. (But maybe you could subclass the TreeNode?)

def __iter__(self):
if self.left: yield from self.left
yield self.val
if self.right: yield from self.right


(In fairness, this last example came from the PEP proposing the yield from syntax: http://www.cosc.canterbury.ac.nz/greg.ewing/python/yield-from/yf_current/Examples/binary_tree.py, and see overview page here: http://www.cosc.canterbury.ac.nz/greg.ewing/python/yield-from/yield_from.html)

• Thank you for the detailed comments! Appreciate it and learned a lot. – Tai Dec 31 '17 at 2:09