# Thread: tree algorithm question

1. Senior Member
Join Date
Jan 2012
Posts
151
Rep Power
9

## tree algorithm question

Can someone talk me through this please:

Algorithm: printExpression(Tree T, Position v)
if T.isInternal(v) then
print ”(”
if T.hasLeft(v) then
printExpression(T, T.left(v))
if T.isInternal(v) then
print the operator stored at v
else
print the value stored at v
if T.hasRight(v) then
printExpression(T, T.right(v))
if T.isInternal(v) then
print ”)”

I am finding it extremely confusing, for eg a tree of:

_
+ /
5 6 6 2

Thanks so much!

2. AN21XX
Join Date
Mar 2012
Location
Munich
Posts
300
Rep Power
9

## Re: tree algorithm question

This is not Java and you do not use the forum code brackets... and you do not name a problem. I guess you need to talk yourself through this, code it in java and then come back if you have a problem, right?

3. ## Re: tree algorithm question

That recursive algorithm prints an infix representation of a tree; your example prints as ((5+6)-(6/2)).

kind regards,

Jos

4. Senior Member
Join Date
Jan 2012
Posts
151
Rep Power
9

## Re: tree algorithm question

Originally Posted by JosAH
That recursive algorithm prints an infix representation of a tree; your example prints as ((5+6)-(6/2)).

kind regards,

Jos
Could you explain how this happens? I don't understand how it works

5. ## Re: tree algorithm question

Follow the algorithm line by line; the first node is an internal node (it's the - node) so a ( is printed followed by (recursively) printing the left sub node; that prints (5+6); because the current node is an internal node its operator is printed (the minus sign) followed by (recursively) printing the right sub node; that prints (6/2) and finally a right parenthesis is printed; that makes ((5+6)-(6/2)).

kind regards,

Jos

6. Senior Member
Join Date
Jan 2012
Posts
151
Rep Power
9

## Re: tree algorithm question

Originally Posted by JosAH
Follow the algorithm line by line; the first node is an internal node (it's the - node) so a ( is printed followed by (recursively) printing the left sub node; that prints (5+6); because the current node is an internal node its operator is printed (the minus sign) followed by (recursively) printing the right sub node; that prints (6/2) and finally a right parenthesis is printed; that makes ((5+6)-(6/2)).

kind regards,

Jos
Thanks very much for the detailed response.
But I am still confused, this is what i get from the algorithm,

first at - is an internal node the ( is printed.
next we recursively call (T, T.left(v)). // where T.left(v) is the +

Now what confuses me here do I carry on with the rest of the if statements ?

Because this is the way im doing it and getting lost:

This means another ( is printed so so far we have ((.

then I call the method again (T, T.left(v)) // where T.left(v) is the 5.

as this node is not internal we print 5. Now i have ((5.

But now I'm confused on what happens next, could you tell me where I'm going wrong please.

Much appreciated and thanks for your time.

7. ## Re: tree algorithm question

That's what recursion is all about, i.e you don't continue with the next line until you have finished the curent code line completely; if you 'dive' down in the recursion, you have to finish it completey before you can 'pop' up again and continue where you left of. After ((5 has been printed you continue printing the nodes' data item (which is a + and you 'dive' down again in the next line of the (recursive) algorithm. For convenience, jot down where you dived down so when you're ready to pop up, check what you've written down so you know where to continue.

kind regards,

Jos

8. Senior Member
Join Date
Jan 2012
Posts
151
Rep Power
9

## Re: tree algorithm question

Originally Posted by JosAH
That's what recursion is all about, i.e you don't continue with the next line until you have finished the curent code line completely; if you 'dive' down in the recursion, you have to finish it completey before you can 'pop' up again and continue where you left of. After ((5 has been printed you continue printing the nodes' data item (which is a + and you 'dive' down again in the next line of the (recursive) algorithm. For convenience, jot down where you dived down so when you're ready to pop up, check what you've written down so you know where to continue.

kind regards,

Jos
Hi Jos, Thanks so much for clearing this up for me. Genuinely appreciated.

9. ## Re: tree algorithm question

Originally Posted by stuckonjava
Hi Jos, Thanks so much for clearing this up for me. Genuinely appreciated.
I'm glad you're understanding it now; once you fully understand the elegance of recursion you'll appreciate it; e.g. tree data structures almost beg for recursion.

kind regards,

Jos

#### Posting Permissions

• You may not post new threads
• You may not post replies
• You may not post attachments
• You may not edit your posts
•