Kth Smallest Element in BST

Problem

Given a binary search tree, write a function kthSmallest to find the kth smallest element in it.

For example:

Input: root = [3,1,4,null,2], k = 1
   3
  / \
 1   4
  \
   2
Output: 1

Input: root = [5,3,6,2,4,null,null,1], k = 3
       5
      / \
     3   6
    / \
   2   4
  /
 1
Output: 3

Solution

class Solution:
    def kthSmallest(self, root: TreeNode, k: int) -> int:
        self.s = None
        self.visited = 0
        self.helper(root, k)
        return self.s
        
    
    def helper(self, root,k):
        if root is None:
            return  
        self.helper(root.left,k)
        self.visited +=1
        if k == self.visited:
            self.s = root.val
            return
        self.helper(root.right, k)
        
#For any problems with inOrder traversal, in the 
#recursive method we have to traverse all the way 
#left before we do any operations

#We are using inOrder traversal approach

#We are keeping count of the nodes visited and 
#comparing this to our input k


#Time: O(h) where h is the height of the tree
#Space: O(h) because of call stack