- Inorder traversal in a BST iterates on the nodes from the smallest one to the larger one.
- From 1, The kth Node that we will reach is the kth Smallest node.
- Once we counted k nodes, return the node's value (there's no need to continue the iteration).
self.count = 0
def kthSmallest(self, root, k):
:type root: TreeNode
:type k: int
return self.inorder(root, k)
def inorder(self, node, k):
# If we reached a None node, we don't increment the count and
# there's no need for more checks
left = self.inorder(node.left, k)
if left is not None:
# This part is the same as 'printing' the node in a normal
# inorder traversal. We return the value only if the current node
# is the kth node that we passed through. This is the only place
# that returns a value, which makes the above and below checks work
self.count += 1
if self.count == k:
right = self.inorder(node.right, k)
if right is not None: