# Pythonic approach with generator

• With generator in python, one very straightforward solution might be:

``````class Solution:
# @param {TreeNode} root
# @param {integer} k
# @return {integer}
def kthSmallest(self, root, k):
for val in self.inorder(root):
if k == 1:
return val
else:
k -= 1

def inorder(self, root):
if root is not None:
for val in self.inorder(root.left):
yield val
yield root.val
for val in self.inorder(root.right):
yield val``````

• Very nice, wish I had thought of that. And I wish we had Python 3 and its `yield from`. Wrote my own version of it now:

``````def kthSmallest(self, root, k):
def inorder(node):
if node:
for val in inorder(node.left):
yield val
yield node.val
for val in inorder(node.right):
yield val
return next(itertools.islice(inorder(root), k-1, k))
``````

• Thanks very much for your unbelievable solution.

• @clockwise9 brilliant use of yield

• @StefanPochmann Nice solution. I'm not too comfortable with yield yet, but would this technically be a O(1) space solution?

• @haxet That would be neat :-). But no. Each of my generators only uses O(1) space, but when I'm at depth d, then I have d nested generators in memory at the same time (one for each level, and their combined state reflect the path to the current node).

• This post is deleted!

• @pyqt Not sure what to explain, it's just inorder traversal and taking the kth element. But here's the `yield from` version:

``````def kthSmallest(self, root, k):
def inorder(node):
if node:
yield from inorder(node.left)
yield node.val
yield from inorder(node.right)
return next(itertools.islice(inorder(root), k-1, k))``````

• Excellent Solution!!

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.