Java Recursive function behavoir

Question

I finished developing a BinaryTree class in Java that builds a Huffman-style binary tree/map to "encode" a phrase into a binary value.

Some of the methods use recursion to populate/traverse the nodes of the tree. I have a method that encodes a string, say test to 01111110001. In order to encode it, I have a function that maps the path of the tree to the node with that character. I also have a function that searches the nodes to find the leaf node of that character.

Everything is working fine: the tree is built, I can search and locate nodes, and the mapping works. When I output the node parameter for the searchNode method, it looks like the code is traversing the tree okay... but it doesn't quit after it finds the node. It finds it multiple times. I have made a few different variations of the method(s) and I can't get it to quit either traversing the entire tree, or stopping once it finds the node the first time.

I'm wondering why the code won't stop after finding the node the first time, and looking for any suggestions on how to optimize it.

public class BinaryTree {

        ---snip ---

            /*
             * searchNode
             * Searches nodes for a value
             *
             * @param n Node to start or focus at
             * @param c char character to search for
             * @return Node containing value
             */
            public Node searchNode(Node n, char c) {
                System.out.println(n);
                if(n != null) {
                    if(n._char == c) { return n; }
                    if(this.searchNode(n._leftChild, c) != null) {
                        return this.searchNode(n._leftChild, c);
                    }
                    if(this.searchNode(n._rightChild, c) != null) {
                        return this.searchNode(n._rightChild, c);
                    }
                }
                return null;
            }






            /*
             * mapPath
             * Maps path with 1s or 0s from root node to
             * node containing char
             *
             * @param n Node to map to
             * @return StringBuilder string of map
             */
            public StringBuilder mapPath(Node n) {
                if(n == null) { return new StringBuilder(1); }

                StringBuilder sb = new StringBuilder(256);
                if(n == this._root || n._parent == null) {
                    sb.insert(0, "0");
                    return sb;
                }
                Node p = n._parent;
                while(p != null) {
                    if(p._leftChild == n) {
                        sb.insert(0, "0");
                    } else {
                        if(p._rightChild == n) {
                            sb.insert(0, "1");
                        }
                    }
                    n = p;
                    p = p._parent;
                }

                return sb;

            }




            /*
             * encodeString
             * Encodes a string with appropriate binary value
             *
             * @param s String to encode
             * @returns encoded String(Builder)
             */
            public StringBuilder encodeString(String s) {
                StringBuilder sb = new StringBuilder(s.length() * 10);
                char[] st = s.toCharArray();
                for(char stt : st) {
                    sb.append(this.mapPath(this.searchNode(this._root, stt)));
                }
                return sb;
            }





            /**
             * @param args the command line arguments
             */
            public static void main(String[] args) {
                BinaryTree bt = new BinaryTree(args[0]);
                bt.buildTree();
                System.out.println(bt.searchNode(bt._root, args[1].toCharArray()[0]));
                //System.out.println(bt.encodeString(args[1]));
            }

        }

The first argument is the phrase or data to encode. The second argument I am passing is the character to search for so java BinaryTree this\ is\ a\ test a uses "this is a test" for the tree and searches for 'a'.

The tree looks like

      14
    /    \
   6      8
  / \     / \
 s  t    _   5
            / \
           i   3
              / \
             a   2
                / \
               h  e

When I run java BinaryTree this\ is\ a\ test i I get the following output:

_ - 14[parent=null *root*]
_ - 6[parent=_ - 14[parent=null *root*]]
s - 3[parent=_ - 6[parent=_ - 14[parent=null *root*]]]
null
null
t - 3[parent=_ - 6[parent=_ - 14[parent=null *root*]]]
null
null
_ - 8[parent=_ - 14[parent=null *root*]]
  - 3[parent=_ - 8[parent=_ - 14[parent=null *root*]]]
null
null
_ - 5[parent=_ - 8[parent=_ - 14[parent=null *root*]]]
i - 2[parent=_ - 5[parent=_ - 8[parent=_ - 14[parent=null *root*]]]]
i - 2[parent=_ - 5[parent=_ - 8[parent=_ - 14[parent=null *root*]]]]
_ - 5[parent=_ - 8[parent=_ - 14[parent=null *root*]]]
i - 2[parent=_ - 5[parent=_ - 8[parent=_ - 14[parent=null *root*]]]]
i - 2[parent=_ - 5[parent=_ - 8[parent=_ - 14[parent=null *root*]]]]
_ - 8[parent=_ - 14[parent=null *root*]]
  - 3[parent=_ - 8[parent=_ - 14[parent=null *root*]]]
null
null
_ - 5[parent=_ - 8[parent=_ - 14[parent=null *root*]]]
i - 2[parent=_ - 5[parent=_ - 8[parent=_ - 14[parent=null *root*]]]]
i - 2[parent=_ - 5[parent=_ - 8[parent=_ - 14[parent=null *root*]]]]
_ - 5[parent=_ - 8[parent=_ - 14[parent=null *root*]]]
i - 2[parent=_ - 5[parent=_ - 8[parent=_ - 14[parent=null *root*]]]]
i - 2[parent=_ - 5[parent=_ - 8[parent=_ - 14[parent=null *root*]]]]
i - 2[parent=_ - 5[parent=_ - 8[parent=_ - 14[parent=null *root*]]]]

The output includes the parents of the node to help me visualize the tree while debugging.

You can see that it found the character 'i' 9 times. Yet when it encodes the string/characters it translates fine to 110.

Answer 1

It doesn't stop the first time you find the node, because you keep on searching after finding it.

if(this.searchNode(n._leftChild, c) != null) {
    return this.searchNode(n._leftChild, c);
}
if(this.searchNode(n._rightChild, c) != null) {
    return this.searchNode(n._rightChild, c);
}

if this.searchNode(n._leftChild, c) finds the node (and returns a non-null result), then you immediately redo the search to return the value. Starting at the root, it will (eventually) search right, to the 8 node, then the 5 node, then search left from the 3 node. Then it will search left from the 3 node again, returning to the 5 node with non-null. The 5 node repeats the search (because it got a non-null value), so you search the 3 node again, find the value, search again (to get the return value), which is returned, and returned again to the 8 node. The 8 node gets a non-null value, and so searches again to return the value (so we visit the 5, and 3, and 3, and 5, and 3 and 3) and return to the root, which again searches the 8 (5 & 3 & 3 and 5 & 3 & 3) and returns.

You want to save your found value, so you can return it!

Node result;
result = this.searchNode(n._leftChild, c);
if (result != null)
   return result;
result = this.searchNode(n._rightChild, c);
if (result != null)
   return result;

Alternately:

Node result = null;

if (n != null) {
    ...
    result = this.searchNode(n._leftChild, c);
    if (result == null)
        result = this.searchNode(n._rightChild, c);
}
return result;