1

(Update)

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.

So far, I really just have (in addition to the helper method provided above):

static ArrayList<String> path = new ArrayList<>();
public static String treePaths(String s)
{

        String[] split = splitTree(s);
        if(split[1].equals("()") && split[2].equals("()"))
        {
            path.add(split[0].toString());
            System.out.println(path.toString());
            return split[0];
        }
        else
        {
            String s2 = "";
            for(int i = 0; i < split.length-1; i++)
                {
                s2 = split[i].toString();
                }
                path.add(split[0].toString());
                return treePaths(s2);

        }

for my recursive method and I'm pretty sure it's wrong already. If anyone can provide any help (especially using the code provided by my professor), I'd be very grateful (even if it's just pointing me in the right direction or helping me understand better what I need to do. Someone helped me before on here, but I'm not sure if it was done the way I needed to do it.

Improve this question
1
  • I think we are supposed to use an arraylist to store the paths as well. Hmm.. Commented Apr 4, 2016 at 14:40

2 Answers 2

Reset to default
1

you are close. the hint for your exit condition is given in the beginning of the helper method. if the length of its input is 2 charactes or less, it returns a 1-size array containing the input. it so happens, that an empty node would trigger this if statement.

Improve this answer
Sign up to request clarification or add additional context in comments.

1 Comment

So sorry, but I'm not sure I follow what you're saying. Should the exit condition for my recursive method (treePaths) be about the length of the input and less so what the input actually is? edit: hm, I guess it should because the splitTree method I'm given splits up the input into something like [a, (b()()), (c()())] (an array of those 3 strings)
1

ok, I am writing a new answer since the last one isn't correct. I have solved the problem (at least the original one that involved printing the paths only).

you are right that you should start with the exit condition of the recursive method.
what is the exit condition? it should be when you reach an end of one path. then you exit and go up the stack of method calls.
looking at the example solution you provided, a path end comes at an element that has two empty elements as children, like elements b and c in the example.
the helper method gives you a distinct output when you give it "an element that has two empty elements"

Continue Apr 5th:
The exit condition is 

if (split[1].equals("()") && split[2].equals("()"))

in this case you have an end-of-path and the path is held by the recursive method stack.
For example: for path a b c
first call to treePaths() encountered a and called 2nd treePaths() which encountered b and it called 3rd treePaths() which encountered c and identified it as end-of-path.
now what is needed to make this scenario happen? how does this shape the input passed to each method?

Improve this answer

24 Comments

It should really exit once the helper method returns node()() because that implies it is at the end of the path. Like for example b()(). Otherwise, it should keep going, right? This is all still a little confusing to me, lol. :(
yes you got it right. by the way, be careful as you wrote split[i] == "()" while you should have used equals. so what is the exit condition? how does the "if" look like?
do you have an answer?? I thought you wanted to do it in steps? or did you solve it all already?
Sorry, I had to take care of something outside and have been working on it now. I'm over-complicating the way to do the if statement, I think. I'm trying to remove the node letter so all that would be left would be the ()() part.
(dang it, can't get the formatting right. i'm removing the node letter so all that is left should be a string of (()()) for base case. This is what I have so far, but it looks SO much more complicated (and probably wrong) than it should have been: public static String[] treePaths(String s) { String[] split = splitTree(s); for(int i = 0; i < split.length; i++) { String test = split[i].toString(); StringBuilder removenode = new StringBuilder(test); removenode.deleteCharAt(1); if(test.equals("(()())")) //base case { return split; } else { }
|

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Start asking to get answers

Find the answer to your question by asking.

Ask question

Explore related questions

See similar questions with these tags.