3

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.

Improve this question
1
  • 2
    Don't you think you need the return value from your recursive calls? For something? Commented Apr 22, 2018 at 1:30

3 Answers 3

Reset to default
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;
}
Improve this answer
Sign up to request clarification or add additional context in comments.

10 Comments

This will crash due a null pointer exception. Can you see why this will happen?
@TimBiegeleisen Are you sure? I tested this and it hasn't crashed for me (yet)
Obviously this can't be called like getNode(null, "foo") but that isn't part of OP's question.
Suppose you don't find the name, i.e. the name is not in the tree. Then how does your recursion know to stop?
Please don't use "Edit:" blocks: meta.stackexchange.com/questions/127639/…
|
1

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.

Improve this answer

16 Comments

Well written answer! (+!)
Does your solution not omit nodes that are not connected to other nodes, eg the first node?
@KamilTomaszJarmusik what makes you think so?
Stream.of(node.right, node.left) - It probably does not include the first node. What do you think about Stream.of(node, node.right, node.left) ?
@KamilTomaszJarmusik no, a SuccessorsFunction<Node> only takes a node and returns its successors. If it were to return itself as a successor, you'd have a graph, not a tree. And as Iterable<N> breadthFirst(N startNode) notes: Traversal not terminating (if the graph has cycles)
|
0

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
Improve this answer

Comments