Build Binary Tree from Preorder Traversal: Stack Overflow Error

Question

I have a tree where the leaves are marked with L and the non-leaf nodes are marked with I. I am given the preorder traversal of the tree. An example is IIILLILILLIIILLLIILILLL. I have to build the huffman tree for this included string. I originally pass in a new Root(), 0, and my treeString for my arguments. TreeString would be the string with the I's and L's pasted above. For some reason my code causes a StackOverflow exception to be thrown. My code is as follows for the makeTree method:

public static void makeTree (BinaryNodeInterface<Character> root, int start, String treeString)
{
    if (treeString.charAt(start)=='L'){

        root.setLeftChild(null);
        root.setRightChild(null);
        return;
    }
    BinaryNodeInterface<Character> leftSide = new BinaryNode<Character>();
    root.setLeftChild(leftSide);
    makeTree(root.getLeftChild(), start++, treeString);
    BinaryNodeInterface<Character> rightSide = new BinaryNode<Character>();
    root.setRightChild(rightSide);
    makeTree(root.getRightChild(), start++, treeString);
}

I have no idea what is causing the stackoverflow exception to be thrown. I would think that my base case at the beginning would return and handle it.

Answer 1

I believe this is the problem:

makeTree(root.getLeftChild(), start++, treeString);

I'm not sure what your approach is, but it looks like if you see an I, your plan is to go to the left node, and start examining the string starting at the next character.

The reason for the infinite recursion is that start++ is a post-increment operator, which means that it gives you the current value of start and then increments it. Thus, each time makeTree calls itself, it calls itself with the same version of start, and thus looks at the same I in the input string.

However, changing it to ++start will not make things work. (It might avoid the stack overflow, but it won't work right.) The reason is that when you call makeTree, you want to give it the starting location of the string where you want the recursive call to start looking--but you also want the recursive call to tell it how much of the string it consumed. That is necessary because, after makeTree calls itself recursively on getLeftChild, you will call it again on getRightChild, and you need to call it with the correct starting point.

Note that each recursive invocation has its own copy of start. Thus, when makeTree calls itself, and the second makeTree increments start, this has no effect on the start that the first makeTree sees.

You'll somehow need each recursive makeTree to tell its caller how much of the string it consumed. Probably, the simplest way to do this is to change the return type to int; you can decide whether you want the function result to be the number of characters consumed, or the index where it stopped scanning, or something similar. Then, after calling makeTree recursively, use the function result to adjust the start parameter. Make sure makeTree returns the correct result, both in the leaf and the non-leaf cases. Be careful to avoid off-by-one errors.