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

## 5 Replies - 8161 Views - Last Post: 30 January 2012 - 11:04 PM

##
**Replies To:** tree traversal: Inorder traversal sequence

### #2 Guest_Neumann*

## Re: tree traversal: Inorder traversal sequence

Posted 26 September 2009 - 08:30 AM

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

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.

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.

1. No, it's being picked according to the rules of the traversal.

2. The rule states to traverse the right subtree, and that's exactly what it's doing. Right subtree's left node is C, root node is D, and right node is E.

3. Think recursively.

This post has been edited by **Neumann**: 26 September 2009 - 08:31 AM

### #3

## Re: tree traversal: Inorder traversal sequence

Posted 26 September 2009 - 09:19 AM

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

1. Traverse the left subtree.

2. Visit the node.

3. Traverse the right 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.

### #4

## Re: tree traversal: Inorder traversal sequence

Posted 27 September 2009 - 01:10 AM

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

### #5

## Re: tree traversal: Inorder traversal sequence

Posted 03 November 2009 - 07:11 PM

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.

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.

### #6

## Re: tree traversal: Inorder traversal sequence

Posted 30 January 2012 - 11:04 PM

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.

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.

Page 1 of 1