Recursive tree encryption method using dfs

Question

This problem is not for an assignment, although it's a somewhat typical "assignment-like" problem that I'm trying to solve in a different way.

I want to write a method that will recursively go through a binary tree using a depth-first search algorithm to find a match for a character. Once it finds the matching character, I want it to return a string that maps the position of the character in the tree using 0s and 1s. "001",for example, would indicate that the character is found by going to the left node of the root node, the left node of that node, and then to the right node of that node.

Here is the code I have so far:

private static String encryptSearch(char c, BinaryNode curNode, String result)
{
    char data = (char) curNode.getData();

    if (data != c)
    {
        if (curNode.hasLeftChild())
        {
            result = result + "0";
            encryptSearch(c, curNode.getLeftChild(), result);
        }
        if (curNode.hasRightChild())
        {
            result = result + "1";
            encryptSearch(c, curNode.getRightChild(), result);  
        }

        result = result.substring(0, result.length()-1);
    }   

    return result;  
} 

The method is initially sent the character to be searched for, the root node, and null for the result. This method returns nothing except 0s. I think there are multiple problems with my code, but the largest one is that when the search reaches a leaf node, it returns. I've been unable to think of a way around this problem while still returning a string. I could easily write a void method that acts on the result string as an external variable, but I don't want to do that for the purpose of the exercise. Any help is appreciated!

Answer 1

Use the mutable StringBuilder instead of String. Also there should be a way to know that you got the result from left one (if any) before searching right one. So I suggest following changes.

private static boolean encryptSearch(char c, BinaryNode curNode, StringBuilder result) {
    char data = curNode.getData();
    if (data != c) {
        boolean found = false;
        if (curNode.hasLeftChild()) {
            found = encryptSearch(c, curNode.getLeftChild(), result);
            if (found) {
                result.insert(0, "0");
                return true;
            }
        }
        if (curNode.hasRightChild()) {
            found = encryptSearch(c, curNode.getRightChild(), result);
            if (found) {
                result.insert(0, "1");
                return true;
            }
        }
        return false; //no result
    }
    return true;
}