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

# tree traversal question

Page 1 of 1## 6 Replies - 1676 Views - Last Post: 17 April 2012 - 08:06 PM

##
**Replies To:** tree traversal question

### #2

## 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

## 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

## 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

## 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

## 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

## Re: tree traversal question

Posted 17 April 2012 - 08:06 PM

Think about it recursively, with the following pseudo-code:

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.

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.

Page 1 of 1