Python recursion - how to exit early -

i've been playing bst (binary search tree) , i'm wondering how exit. following code i've written find kth smallest. recursively calls child node's find_smallest_at_k, stack list passed function add elements in inorder. solution walks nodes inorder , have select kth item "stack" outside function.

def find_smallest_at_k(self, k, stack, i):     if self none:         return      if (self.left not none):          = self.left.find_smallest_at_k(k, stack, i)       print(stack, i)     stack.insert(i, self.data)     += 1     if == k:          print(stack[k - 1])          print "returning"       if (self.right not none):          = self.right.find_smallest_at_k(k, stack, i)       return  

it's called this,

our_stack = [] self.root.find_smallest_at_k(k, our_stack, 0)  return our_stack[k-1]  

i'm not sure if it's possible exit function. if k 1, don't have walk nodes find first element. doesn't feel right pass list outside function - feels passing pointers function in c. suggest better alternatives i've done far?

passing list arguments: passing list argument can practice, if make function tail-recursive. otherwise it's pointless. bst there 2 potential recursive function calls done, it's bit of tall ask.

else can return list. don't see necessity of variable i. anyway if absolutely need return multiples values, can use tuples return i, stack , i, stack = root.find_smallest_at_k(k).

fast-forwarding: fast-forwarding, note right nodes of bst parent node bigger parent. if descend tree on right children, you'll end growing sequence of values. first k values of sequence smallest, it's pointless go right k times or more in sequence.

even in middle of descend go left @ times, it's pointless go more k times on right. bst properties ensures if go right, subsequent numbers below in hierarchy greater parent. going right k times or more useless.

code: here pseudo-python code made. it's not tested.

def findksmallest( self, k, rightsteps=0 ):     if rightsteps >= k: #we went right more k times         return []     leftsmallest = self.left.findksmallest( k, rightsteps ) if self.left != none else []     rightsmallest = self.right.findksmallest( k, rightsteps + 1 ) if self.right != none else []     mysmallest = sorted( leftsmallest + [self.data] + rightsmallest )     return mysmallest[:k] 

edit other version, following comment.

def findksmallest( self, k ):     if k == 0:         return []     leftsmallest = self.left.findksmallest( k ) if self.left != none else []     rightsmallest = self.right.findksmallest( k - 1 ) if self.right != none else []     mysmallest = sorted( leftsmallest + [self.data] + rightsmallest )     return mysmallest[:k] 

note if k==1, indeed search of smallest element. move right, returns [], contributes nothing.