Java Recursion and Binary Tree

Question

My class has been working on using recursion to create things like the Towers of Hanoi, Fibonacci, and all that fun stuff. The problem is, I don't really understand everything very well. I understand the general concept of recursion, but putting it into practice when making a program feels so complicated to me. I get that it's calling the method over and over typically under it reaches a base case where it exits, but it's hard for me to write code that does what I want it to do.

We are working on binary trees right now. We are supposed to use some code provided by my professor to split up a tree, then write a recursive method to print out all the paths that the tree contains. Our input will be something like (a(b()())(c()())) which would be a tree of:

 a
b c

b and c would have 0 children below them. (a) is a possible node, and () would be an empty node which would be the end of that path. Our goal is to print out all the paths, so for my example, the output would be:

a b

a c

The code we are given includes a helper method that we can use to write our recursive method:

public class BinaryTree {


public static void main(String[] args) {
    Scanner scan = new Scanner(System.in);
    String tree = scan.nextLine();//correct format : (a()())
    String[] t = splitTree(tree);
    System.out.println(Arrays.toString(t));

}
public static String[] splitTree(String tree)
{
    //expected format
    //(node tree tree)
    //0 1 2-x x-(length-2) length-1
    if(tree.length() <= 2)//tree not long enough to process
        return new String[]{tree};

    String[] temp = new String[3];
    temp[0] = "" + tree.charAt(1);//grab tree node
    tree = tree.substring(2, tree.length()-1);//remove node and outer paren
    int parenCount = 0;//count of open paren
    int endTreeOne = 0;//end of first tree
    for(int i = 0; i < tree.length(); i++)
    {
        if(tree.charAt(i) == '(')
            parenCount++;
        if(tree.charAt(i) == ')')
            parenCount--;
        if(parenCount == 0)
        {
            endTreeOne = i;
            break;//ends for loop early
        }
    }
    temp[1] = tree.substring(0, endTreeOne+1);//left tree
    temp[2] = tree.substring(endTreeOne+1);//right tree
    return temp;
}

This method basically converts a string of characters like (a(b()())(c()())) and makes them [a, (b()()), (c()())]. Splitting the tree up basically.

I'm just really not sure how to proceed from here to write my recursive method. I feel pretty lost honestly (and frustrated as a result). I think I need to make my method check for if "()" exists, then that is the end of a path. Would that be my base case to exit out of the loop I'd need? I'm not sure how to specify which side of the tree to take as well. If someone can provide any help, tips, or get me on the right train of thought for tackling this, I'd greatly appreciate it.

Answer 1

I feel like the "printing paths" step will be easier with an object of a tree, so let's define that.

The toString method is recursively implemented to re-print what you will parse into this object.

public class BinaryTreeNode {
    public String root;
    public BinaryTreeNode left;
    public BinaryTreeNode right;

    public BinaryTreeNode(String root) {
        this.root = root;
    }

    @Override
    public String toString() {
        String s = root;

        if (left != null) {
            s += left.toString();
        } else {
            s += "()";
        }

        if (right != null) {
            s += right.toString();
        } else {
            s += "()";
        }

        return "(" + s + ")";
    }
}

I also have a helper-method to count the parenthesis, and throw an error if any mismatch.

private static int getParenCount(String s) {
    int parenCount = 0;
    int opened = 0;

    for (int i = 0; i < s.length(); i++) {
        char c = s.charAt(i);
        if (c == '(') {
            parenCount++;
            opened++;
        } else if (c == ')') {
            parenCount++;
            opened--;
        }
    }
    if (opened != 0) {
        throw new IllegalArgumentException("Paren mismatch." + s + " is not a valid tree.");
    }
    return parenCount;
}

Then, with regards to parsing the string, I left in some helpful code-comments.

public static BinaryTreeNode getTree(String treeString) {
    // Initialize variables
    String root;
    String leftTree;
    String rightTree;
    BinaryTreeNode tree = new BinaryTreeNode("");

    System.out.println("Input: " + treeString);

    if (treeString.equals("()")) {
        System.out.println("Empty tree. Returning!");
        return null;
    }

    // Check for even parenthesis
    int parenCount = getParenCount(treeString);
    if (parenCount % 2 == 0) {

        // Strip the outside parenthesis
        treeString = treeString.substring(1, treeString.length()-1);
        System.out.println("tree: " + treeString);

        // Find the first '(' because the root is everything before it
        int leftTreeStart = treeString.indexOf('(');
        root = treeString.substring(0, leftTreeStart);

        // Find the complete left-tree
        int leftTreeEnd = leftTreeStart + 1;
        int leftTreeParenCount = 0;
        for (int i = leftTreeStart-1; i < treeString.length(); i++) {
            char c = treeString.charAt(i);
            if (c == '(') {
                leftTreeParenCount++;
            } else if (c == ')') {
                leftTreeParenCount--;
                if (leftTreeParenCount == 0) {
                    leftTreeEnd = i;
                    break;
                }
            }
        }

        System.out.println("root: " + root);
        tree.root = root;

        leftTree = treeString.substring(leftTreeStart, leftTreeEnd + 1);
        System.out.println("\nleft: " + leftTree);
        System.out.println("Recurse left...");
        tree.left = getTree(leftTree); // recurse here

        // The right-tree is just the remainder of the string
        rightTree = treeString.substring(leftTreeEnd + 1);
        System.out.println("\nright:" + rightTree);
        System.out.println("Recurse right...");
        tree.right = getTree(rightTree); // recurse here

    }

    return tree; 
}