finding all numbers less than x in a BST

Question

how would i do this? I am not sure when I would stop the bst search.

Answer 1

Not sure if this is exactly what you are looking for or not, but binary search tree algorithms are classic and the internet is full of them. http://www.algolist.net/Data_structures/Binary_search_tree/Lookup - should at least get you going in the right direction (you would want to modify the 'found' condition and return a 'collection' instead of a bool).

Answer 2

If each node of your tree has a field numLeft that tells you how many nodes there are in its left subtree (counting itself too), then you can do this in O(log N)

Just keep adding numLeft to a global result variable for each node whose value is less than x:

countLessThan(int x, node T)
    if T = null
        return
    if T.value >= x
        countLessThan(x, T.left) // T.left contains only numbers < T.value and T.right only numbers > T.value
    else
        globalResult += T.numLeft
        countLessThan(x, T.right)

This will only count the numbers. If you want to print them, you need to write a depth first traversal that will print a subtree given as parameter. You can find plenty of those online, so I won't post that.

Answer 3

If you need list of number you'll need to traverse tree anyway. For BST you can do traversing from lowest to highest.
But if you need subtree which represents lowest numbers:

def splitLowerTree(x, node):
  if node is None: return None
  elif node.value == x: return node.left
  elif node.value < x:
      if node.right is None: return node
      else: return Node(node.value, left = node.left, right = splitLowerTree(x, node.right))
  else: return splitLowerTree(x, node.left)