In Order Bst Traversal: Find

I am trying to find the kth smallest element of binary search tree and I have problems using recursion. I understand how to print the tree inorder/postorder etc. but I fail to retu

Solution 1:

If this is an academic exercise, make traverseInOrder (or similar method tailored to the purpose) return the number of children it visited. From there things get simpler.

If this isn't academic, have a look at http://stromberg.dnsalias.org/~dstromberg/datastructures/ - the dictionary-like objects are all trees, and support iterators - so finding the nth is a matter of zip(tree, range(n)).

Solution 2:

You could find the smallets element in the binary search tree first. Then from that element call a method to give you the next element k times.

For find_smallest_node method, note that you can traverse all the nodes "in-order" until reach to smallest. But that approach takes O(n) time.

However, you do not need a recursion to find the smallest node, because in BST smallest node is simply the left most node, so you can traverse the nodes until finding a node that has no left child and it takes O(log n) time:

classBST(object):

  deffind_smallest_node(self):
    if self.root == None:
      return
    walking_node = self.root
    smallest_node = self.root
    while walking_node != None:
      if walking_node.data <= smallest_node.data:
        smallest_node = walking_node
      if walking_node.left != None:
        walking_node = walking_node.left
      elif walking_node.left == None:
        walking_node = Nonereturn smallest_node


  deffind_k_smallest(self, k):
    k_smallest_node = self.find_smallest_node()
    if k_smallest_node == None:
      returnelse:
      k_smallest_data = k_smallest_node.data
    count = 1while count < k:
      k_smallest_data = self.get_next(k_smallest_data)
      count += 1return k_smallest_data


  defget_next (self, key):
   ... 

It just requires to keep the parent of the nodes when inserting them to the tree.

classNode(object):
  def__init__(self, data, left=None, right=None, parent=None):
    self.data = data
    self.right = right
    self.left = left
    self.parent = parent

An implementation of the bst class with the above methods and also def get_next (self, key) function is here. The upper folder contains the test cases for it and it worked.