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.

Answer 3

I would suggest taking tail recursions into account, since performance-wise this is a major factor :

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.name.equals(name)) {
        return currentNode;
    } else {
        // Tail recursions
        if(currentNode.left == null) {
            return getNode(currentNode.right, name);
        }
        else if(currentNode.right == null) {
            return getNode(currentNode.left, name);
        }
        // Non Tail recursion
        else {
        retrieved = getNode(currentNode.left, name);

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

Attached is the full code which was executed on an online compiler:

public class MyClass {
    static class Node {
    public String name;
    public Node left;
    public Node right;

    Node(String name) {
        this.name = name;
        right = null;
        left = null;
    }

    @Override
    public String toString() {
        return "name = " + name + " hasLeft = " + (left != null) + " hasRight = " + (right != null);
    }

}

static class Tree {

    Node root;

    public Node getRoot() {
        return root;
    }

    private Node addRecursive(Node current, String value) {
    if (current == null) {
        return new Node(value);
    }

    if (value.compareTo(current.name) < 0) {
        current.left = addRecursive(current.left, value);
    } else if (value.compareTo(current.name) > 0) {
        current.right = addRecursive(current.right, value);
    } else {
        // value already exists
        return current;
    }

    return current;
    }

    public Tree add(String value) {
        root = addRecursive(root, value);
        return this;
    }

    public void traverseInOrder(Node node) {
        if (node != null) {
            traverseInOrder(node.left);
            System.out.print(" " + node.name);
            traverseInOrder(node.right);
        }
    }

    public void traverseInOrder() {
        traverseInOrder(root);
         System.out.println("");
    }

}

public static void main(String args[]) {
    Tree tree = new Tree();
    tree.add("a").add("ab").add("bbb").add("cc").add("zolko").add("polip").traverseInOrder();

    Node found = getNode(tree.getRoot(),"vv");
    System.out.println(found);
    found = getNode(tree.getRoot(),"ab");
    System.out.println(found);
    found = getNode(tree.getRoot(),"polip");
    System.out.println(found);
    found = getNode(tree.getRoot(),"java");
    System.out.println(found);
    found = getNode(tree.getRoot(),"zolko");
    System.out.println(found);

}

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.name.equals(name)) {
        return currentNode;
    } else {
        // Tail recursions
        if(currentNode.left == null) {
            return getNode(currentNode.right, name);
        }
        else if(currentNode.right == null) {
            return getNode(currentNode.left, name);
        }
        // Non Tail recursion
        else {
        retrieved = getNode(currentNode.left, name);

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

And the outputs of the main method execution:

 a ab bbb cc polip zolko
null
name = ab hasLeft = false hasRight = true
name = polip hasLeft = false hasRight = false
null
name = zolko hasLeft = true hasRight = false