CareerCup

Do an inorder traversal, stopping when come to a larger key.

Possible pseudo-code

void printSmaller (Tree *root, int k) {
    if (!root) return;
        
    printSmaller(root->left, k);
    if (root->data < k) {
        printf("%d ", root->data);
        printSmaller(root->right, k);
    }
}

Just INORDER-WALK its left child.

o traverse to the key element
o if the element is a left-child(node->parent->left == node), then traverse the node->left subtree
o if the element is a right-child(node->parent->right == node), then traverse the node->parent->left subtree followed by node->parent followed by node->left subtree.
<will post working code soon>

The idea is simple. As you move right in the BST, in-order print the left subtree and the current node. As you move left in the subtree, print nothing since the search key is bigger than the current node key. If you find the key, print the left subtree and return.

I do a find() first so if the key doesn't exist, I simply return and print nothing. I guess that increases the running time by a constant factor and I'm sure it can be optimized.

def walkLeft(self, inputKey):
current = self._root

if self.find(inputKey) == None:
return

while current != None:
currentKey = current.getKey()
if inputKey == currentKey:
self.walkInOrder(current.getLeft())
return
elif inputKey > currentKey:
self.walkInOrder(current.getLeft())
print str(current.getKey()) + ',' + str(current.getData())
current = current.getRight()
else:
current = current.getLeft()

find(root,key)
{
      if(root == NULL) return;
      
      if(root <= key)
      {
             print_all_left_nodes(root);
             find(root->right,key);
      }
      else
             find(root->left,key);
}

Here is a Java version:

public void printAllValuesSmallerThen(Node node, Integer value) {
		if (node == null)
			return;
		
		this.printAllValuesSmallerThen(node.getLeftChild(), value);
		if (node.getData() > value)
			return;
		else
			System.out.print(node.getData() + " ");
		this.printAllValuesSmallerThen(node.getRightChild(), value);		
	}

void printsmall(tree *node,int data)
{
if(node)
{
printsmall(node->left,data);
if(node->item < data)
printf("%d ",node->item);
printsmall(node->right,data);
}
return;
}

void print_till(mynode* root, int elt){
if(root){
print_till(root->left, elt);
if(root->value<=elt){
printf("%d ", root->value);
print_till(root->right, elt);
}
}
}