Find a node that holds a given string in a binary tree using recursion

Question

I have this method that uses recursion to find a node that holds a specified String in a binary tree. The issue is that it returns null, when it should return the node that holds the specified name, and I'm not sure why.

Here's the method:

public Node getNode(Node currentNode, String name) { 
    Node retrieved = null;
    if (currentNode.getName().equals(name)) { retrieved = currentNode; }
    else 
    {
        if (currentNode.right != null) {
            getNode(currentNode.right, name);
        } 
        if (currentNode.left != null) {
            getNode(currentNode.left, name);
        }
    }
    return retrieved;
}

Any insight into what may be the problem would be appreciated.

Answer 1

You need to capture the return value of your two recursive calls. Otherwise you're doing recursion "for nothing" and throwing away the result of the recursion.

public Node getNode(Node currentNode, String name){ 
    Node retrieved = null;
    if (currentNode.getName().equals(name)) { retrieved = currentNode; }
    else 
    {
        if (currentNode.right != null){
            retrieved = getNode(currentNode.right, name);
        } 
        if (retrieved == null && currentNode.left != null){
            retrieved = getNode(currentNode.left, name);
        }
    }
    return retrieved;
}

The following solution is arguably better style because you leave null checks for a base case. Notice how you no longer need to check currentNode.right != null or currentNode.left != null, as they're covered by the base case after one more recursive step.

public static Node getNode(Node currentNode, String name){
    // Base case: currentNode is null, nothing left to search
    if (currentNode == null) {
        return null;
    }

    Node retrieved = null;
    if (currentNode.getName().equals(name)) {
        retrieved = currentNode;
    } else {
        // Try to search right subtree
        retrieved = getNode(currentNode.right, name);

        // If not found in right subtree, then search left subtree
        if (retrieved == null){
            retrieved = getNode(currentNode.left, name);
        }
    }
    return retrieved;
}

Answer 2

Solution

getNode(currentNode.right, name);

You call the getNode(...) method but you don't do anything with it.

A better solution

If you are willing to use googles Guava (must-have for every project in my opinion) and java 8, you can do the following:

public static final Traverser<Node> TREE_TRAVERSER = 
        Traverser.forTree((SuccessorsFunction<Node>) node ->
                Stream.of(node.right, node.left)
                        .filter(Objects::nonNull)
                        .collect(Collectors.toList()));

And then call it where ever you want to traverse the tree:

for (Node n : TREE_TRAVERSER.depthFirstPreOrder(root)) {
    if (n.getName().equals("foo")) {
        // todo: do stuff with node foo
    }
}

The java 8 way of traversing the tree would then be:

Iterable<Node> nodes = TREE_TRAVERSER.depthFirstPreOrder(root);
Optional<Node> result = StreamSupport.stream(nodes.spliterator(), false)
        .filter(n -> n.getName().equals("foo")) // find node with name "foo"
        .findAny(); // we assume there is <= 1 node, so we take any.
// node.isPresent() to check if you found a Node and result.get() to get the Node

---

How does this work?

Well, Guava has this nice class called a Traverser<N>. You just give it one parameter, which is the SuccessorsFunction<N>. It takes any object N and returns a Iterable<? extends N>, which are the child nodes.

We use Streams to do this. First we create a Stream of the two child nodes. We then filter them to only have a Stream of nonNull Nodes and collect them in a List (since the SuccessorsFunction<Node> wants to return a Iterable<Node>).

This Traverser<N> only has to be created once, so we made it public static final. You can now choose an iteration order. We chose depthFirstPreOrder, which returns an Iterable<N> we can iterate over

---

If you haven't heard of Streams before, I would recommend this turorial.