Binary Tree Search for values less than

Question

I'm creating an algorithm for a binary tree for university work and I need to develop an algorithm that efficiently find all the values smaller than a specified value (they need to be in order).

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

This is the solution I came up with (the graph above is in case you forgotten how a binary tree looks like).

private BinaryTreeNode root;
public int[] getBeforeJoinedNum(int num){
        usersInOrder = new ArrayList<User>();
        beforeNum(num, root);
        return usersInOrder;
}

private void beforeNum(int num, BinaryTreeNode n){
        if (n != null){
            beforeNum(num, n.getLeft());
            int nodeValue = n.getValue();
            if (num<nodeValue){
                usersInOrder.add(n.getValue());
                beforeNum(num, n.getRight());
            }
        }
    }

The problem with this algorithm is that it does unnecessary comparisons. For example If i want all the number smaller than 10, the code will check everything left of 9 (i.e. 1,5,8) if it is smaller than 10, whereas it should be quite obvious anything smaller than 9 will of course should be in the list, without any need of a comparison.

How can I make this algorithm more efficient? Unfortunately, I cannot use the Java collection framework, as the data structure is the point of the coursework.

Answer 1

For subtrees of which you know that they fulfill the property, just do a standard in-order traversal:

private void addAll(UserNode n) {
    if (n == null) return;
    addAll(n.getLeft());
    usersInOrder.add(n.getValue());
    addAll(n.getRight());
}

private void beforeNum(int num, UserNode n){
    if (n == null) return;
    if (n.getValue() < num) {
        addAll(n.getLeft());
        usersInOrder.add(n.getValue());
        beforeNum(num, n.getRight());
    } else {
        beforeNum(num, n.getLeft());
    }
}

Note that I also fixed a logic bug in beforeNum: You mixed up < with > and you didn't traverse the right subtree under the correct circumstances.

Answer 2

Ever heard of inorder search? below is a sample code. Modify it so that it accepts one parameter which the "user node" and stops traversing when it still lesser than the "usernode"

public void inOrderTraverse(Node root){
        if(root != null){
            inOrderTraverse(root.getLeft());
            System.out.print("  "+root.getData());
            inOrderTraverse(root.getRight());
        }

    }

Here's a quick modified version:

public void inOrderTraverse(Node root,UserNode n){
        if(root != null&&root.compareTo(n)<0){
            inOrderTraverse(root.getLeft());
            System.out.print("  "+root.getData());
            inOrderTraverse(root.getRight());
        }

    }

You'll need to traverse all the nodes at the left anyway.