[NecroWinter]

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

[macosxnerd101]

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.

[NecroWinter]

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

[blackcompe]

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

[macosxnerd101]

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

[NecroWinter]

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

[macosxnerd101]

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.