[ethereal1m]

Greetings experts,
I need help to get a grip on understanding of binary tree in inorder transversal.

according to wiki:
To traverse a non-empty binary tree in inorder, perform the following operations recursively at each node:
1. Traverse the left subtree.
2. Visit the node.
3. Traverse the right subtree.

Suppose there is a binary tree like this:


the sequence of Inorder traversal sequence will be A, B, C, D, E, F, G, H, I.

Question:
1. I assume A is picked up at random. Is this correct?
2. From A it goes to B, as it is said that from left to root, but how come from B it goes to C, not D since it is said that after visit the node, traverse the right subtree?
3. From this point, I just totally lost. I need more explanation on the sequence.

Regards,
Ethereal1m

[baavgai]

ethereal1m, on 26 Sep, 2009 - 03:22 AM, said:

1. Traverse the left subtree.
2. Visit the node.
3. Traverse the right subtree.

Yep, those are the rules.

Looking at your tree, you start out at the F node. However, you're not really considering that value, because F has a left leaf...

Not really sure how far to take this. Given the tree shown, here's what a partial traversal looks like:

Start F
	Has a Left branch
		Walk to B
			Has a Left branch
				Walk to A
					No Left
*					Visit A
					No Right
					Back(A)
*			Visit B
			Has a Right branch
				Walk to D
					Has a Left branch
						Walk to C
							No Left
*							Visit C
							No Right
							Back(C)
*					Visit D
						Has a Right branch
							Walk to E
								No Left
*								Visit E
								No Right
								Back(E)
					Back(D)
			Back(B)
*	Visit F
	Has a Right branch
	...

Hope that helps.

[ethereal1m]

OK, thanks guys for the replies. I didn't get a recursive notion properly. I do now.

[rudreshwar]

baavgai, on 26 Sep, 2009 - 08:19 AM, said:

ethereal1m, on 26 Sep, 2009 - 03:22 AM, said:

1. Traverse the left subtree.
2. Visit the node.
3. Traverse the right subtree.

Yep, those are the rules.

Looking at your tree, you start out at the F node. However, you're not really considering that value, because F has a left leaf...

Not really sure how far to take this. Given the tree shown, here's what a partial traversal looks like:

Start F
	Has a Left branch
		Walk to B
			Has a Left branch
				Walk to A
					No Left
*					Visit A
					No Right
					Back(A)
*			Visit B
			Has a Right branch
				Walk to D
					Has a Left branch
						Walk to C
							No Left
*							Visit C
							No Right
							Back(C)
*					Visit D
						Has a Right branch
							Walk to E
								No Left
*								Visit E
								No Right
								Back(E)
					Back(D)
			Back(B)
*	Visit F
	Has a Right branch
	...

Hope that helps.

[eDxOn007]

baavgai, on 26 September 2009 - 09:19 AM, said:

ethereal1m, on 26 Sep, 2009 - 03:22 AM, said:

1. Traverse the left subtree.
2. Visit the node.
3. Traverse the right subtree.

Yep, those are the rules.

Looking at your tree, you start out at the F node. However, you're not really considering that value, because F has a left leaf...

Not really sure how far to take this. Given the tree shown, here's what a partial traversal looks like:

Start F
	Has a Left branch
		Walk to B
			Has a Left branch
				Walk to A
					No Left
*					Visit A
					No Right
					Back(A)
*			Visit B
			Has a Right branch
				Walk to D
					Has a Left branch
						Walk to C
							No Left
*							Visit C
							No Right
							Back(C)
*					Visit D
						Has a Right branch
							Walk to E
								No Left
*								Visit E
								No Right
								Back(E)
					Back(D)
			Back(B)/>
*	Visit F
	Has a Right branch
	...

Hope that helps.