How to find a node in a binary search tree

Question

I was reading about binary trees in java. I found this code :

public BSTNode findNode(Comparable val){
        int delta = val.compareTo(value);
        // the value is less than this.value
        if(delta < 0){
            // if there is a leftChild, return left.findNode(val)
            // there is no leftChild, so the val does not exist
            // in the node, so return null
            return (left!= null)? left.findNode(val): null;
        }
        // else if the value is greater than this.value
        else if (delta > 0){
            // if there is a rightChild, then return right.findNode(val)
            // else, there is no rightChild, return null
            return (right != null)? right.findNode(val): null;
        }
        // else, dela == 0, so we have found the node with that
        // val, return the node
        return this;
    }

I do not understand how this works :

return (left!= null)? left.findNode(val): null;
return (right != null)? right.findNode(val): null;

Can you rewrite it in another way?

Thanks

Answer 1

OK, let's go step by step. First of all, I'll focus on the algorithm itself.

class Node<T> {
    T value;
    Node left;
    Node right;
}

You are guaranteed that all values to the left are smaller or equal than value and all values to the right are larger or equal than value. This makes searching easier. If you're looking for element val you simply compare it to the value in current Node. If desired element is equal current element, you've found it. If it's greater it can only be in the right part of a tree. Otherwise in the left side.

It can happen that the element isn't here. It happens if you see that it should be to the left/right from the current node, but there is nothing there (null).

So the BinaryTreeSearch is:

T search(Node tree, T val) {
    int delta = tree.getValue.compareTo(val);
    if (delta == 0) {
        return tree.getValue;
    } else if (delta > 0) {
        return search(tree.getRight(), val);
    } else {
        return search(tree.getLeft(), val);
    }
}

But wait... this leads to the NPE if the item isn't here. Let's modify it:

T search(Node tree, T val) {
    if (tree == null)
         return null;
    int delta = tree.getValue.compareTo(val);
    if (delta == 0) {
        return tree.getValue;
    } else if (delta > 0) {
        return search(tree.getRight(), val);
    } else {
        return search(tree.getLeft(), val);
    }
}

This can be also rewritten this way:

T search(Node tree, T val) {
    int delta = tree.getValue.compareTo(val);
    if (delta == 0) {
        return tree.getValue;
    } else if (delta > 0) {
        if (tree.getRight() == null) 
            return null;
        return search(tree.getRight(), val);
    } else {
        if (tree.getLeft() == null)
            return null;
        return search(tree.getLeft(), val);
    }
}

But here comes the ternary operator which is shortened and simplified if-else.

result = testCondition ? value1 : value2

which is the same as

if (testCondition) {
    result = value1;
} else {
    result = value2;
}

Another conditional operator is ?:, which can be thought of as shorthand for an if-then-else statement (discussed in the Control Flow Statements section of this lesson). This operator is also known as the ternary operator because it uses three operands. In the following example, this operator should be read as: "If someCondition is true, assign the value of value1 to result. Otherwise, assign the value of value2 to result."

So we finally receive:

T search(Node tree, T val) {
    int delta = tree.getValue.compareTo(val);
    if (delta == 0) {
        return tree.getValue;
    } else if (delta > 0) {
        return (tree.getRight() == null) ? null : search(tree.getRight(), val);
    } else {
        return (tree.getLeft() == null) ? null : search(tree.getLeft(), val);
    }
}

Answer 2

They can be rewritten as:

if(left != null) {
  return left.findNode(val);
} else {
  return null;
}

and

if(right != null) {
  return right.findNode(val);
} else {
  return null;
}

Hope this helps :-).