tree traversal question

Page 1 of 1

6 Replies - 1795 Views - Last Post: 17 April 2012 - 08:06 PM

#1 NecroWinter

• D.I.C Regular

Reputation: 38
• Posts: 333
• Joined: 21-October 11

tree traversal question

Posted 17 April 2012 - 07:31 PM

i just cant make this make any sense.

In order is left root right

http://en.wikipedia....aversal#Example

If left root right is followed then it SHOULD be:
ABDCEFGIH
i can see how i and h are exchanged if you simply go to the node furthest left in the graph but this is taking some imagination.

ive coded these things before using recursion and it makes sense that way, but the way they teach this is just... weird, almost chaotic

Is This A Good Question/Topic? 0

Replies To: tree traversal question

#2 macosxnerd101

• Games, Graphs, and Auctions

Reputation: 12242
• Posts: 45,328
• Joined: 27-December 08

Re: tree traversal question

Posted 17 April 2012 - 07:39 PM

The definition is applied recursively. So at G, the I node is treated as a subtree. So I is the root, H is the left child, and there is no right child. So H must be visited before I.

#3 NecroWinter

• D.I.C Regular

Reputation: 38
• Posts: 333
• Joined: 21-October 11

Re: tree traversal question

Posted 17 April 2012 - 07:47 PM

macosxnerd101, on 17 April 2012 - 07:39 PM, said:

The definition is applied recursively. So at G, the I node is treated as a subtree. So I is the root, H is the left child, and there is no right child. So H must be visited before I.

So how do you explain C?

I find that to be much more difficult to understand

#4 blackcompe

• D.I.C Lover

Reputation: 1159
• Posts: 2,547
• Joined: 05-May 05

Re: tree traversal question

Posted 17 April 2012 - 07:52 PM

Just remember this for an in-order traversal: Whenever you arrive at a node, try to go left. If you can't (NULL or 'visited' left child), then try to go the right. If you can't go right (NULL or 'visited' right child), mark the node as 'visited', print it, and go back to the parent and then mark the parent as 'visited'. The process starts all over again with the parent as the current node. Now according to this logic you have:

```arrive at F, I can go left, go there

arrive at B, I can go left, go there

arrive at A, I can't go left (NULL) and I can't go right (NULL), mark as visited, go to parent and mark it as visited.

arrive at B, I can't go left (visited), but I can go right, go there

arrive at D, I can go left, go there

arrive at C, I can't go left (NULL) and I can't go right (NULL), mark as visited, go to parent and mark it as visited.

arrive at D ....
```

This post has been edited by blackcompe: 17 April 2012 - 07:58 PM

#5 macosxnerd101

• Games, Graphs, and Auctions

Reputation: 12242
• Posts: 45,328
• Joined: 27-December 08

Re: tree traversal question

Posted 17 April 2012 - 07:53 PM

You copied the in-order traversal wrong from Wikipedia. The actual ordering is:

Quote

Inorder traversal sequence: A, B, C, D, E, F, G, H, I (left, root, right); note how this produces a sorted sequence

#6 NecroWinter

• D.I.C Regular

Reputation: 38
• Posts: 333
• Joined: 21-October 11

Re: tree traversal question

Posted 17 April 2012 - 07:59 PM

macosxnerd101, on 17 April 2012 - 07:53 PM, said:

You copied the in-order traversal wrong from Wikipedia. The actual ordering is:

Quote

Inorder traversal sequence: A, B, C, D, E, F, G, H, I (left, root, right); note how this produces a sorted sequence

I never copied it to begin with. I was following left root right and am looking for an explanation as to how to make it work.

blackcompe's idea makes sense, and produces the right answer which is helpful, but im still trying to reconcile the formal way

#7 macosxnerd101

• Games, Graphs, and Auctions

Reputation: 12242
• Posts: 45,328
• Joined: 27-December 08

Re: tree traversal question

Posted 17 April 2012 - 08:06 PM

Think about it recursively, with the following pseudo-code:
```inorder(TreeNode root)
if(root is null) return

inorder(root->left)
print root->element
inorder(root->right)

```

Now when you invoke inorder(root) passing the F node from the Wikipedia example, it starts by going left until you hit A. Then you go back up to B, then back down to D. Rather than printing D, you print C first, then D, then back down to E. Walk through the pseudo-code with the tree.

Hopefully this helps clear things up.