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.