Algorithm to find all values less than a given value in a binary search tree

Question

Having a Binary Search Tree of int create a linked list of all the integers less than a given integer x value.

What I've tried?

1)brutal solution(inefficient)

An inorder visit of the BST, I insert a node in the list for every integer int the Bst, and then I free every node of the list starting from x

2)more efficient but wrong

I make a search and when I find x, I create a list with an in-order visit of the left son of the node where I've found x.

It's obvious wrong, for example considering the follow BST:

                         10
                        /  \
                       9    11
                      /       \
                     5         15
                    / \        / \
                   1   8      13  19
                             /  \
                            12  14

with this solution if x=15 I just consider {12,13,14}, it would work just for x=root.

The question is How can I do?

Answer 1

If you store the parent node of each node, a more efficient solution can be implemented, as long as you don't care about the order of the elements in the result list:

1. Create a new list to save the result
2. Find the node of interest
3. Add to the list all the nodes in the left subtree of the node found on step 2, using any traversal you fancy (in-order, pre-order, etc.)
4. Starting from the parent of the node found on step 2, go up through all the parents adding each node in the way until the current node is either the root node or a node to the left of its parent
5. Finally, add all the elements to the left of the node found on step 4, again using any traversal

Answer 2

Pseudocode. v is current vertex, ans is the answer list, someTraversal is a method traversing through the tree and returning a list of its elements.

1. v := root, ans := []
   
2. if v.value > x
   then v := v.left, goto 2;
   
3. ans.append( someTraversal ( v.left ))
   
4. if v.value = x
   then return ans;
   
5. ans.append( v.value )
   
6. v := v.right;
   
7. goto 2;

Answer 3

Here's a modified version of an inorder traversal that terminates when a node's value is > x.

def nums_less_than(n, x, l=None):
  if l == None:
    l = []
  if n.left:
    nums_less_than(n.left, x, l)
  if n.value < x:
    l.append(n.value)
    if n.right:
      nums_less_than(n.right, x, l)
  return l