# tree traversal: Inorder traversal sequence

Page 1 of 1

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

### #1 ethereal1m

Reputation: 3
• Posts: 227
• Joined: 30-June 09

# tree traversal: Inorder traversal sequence

Posted 26 September 2009 - 02:22 AM

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

Is This A Good Question/Topic? 0

Reputation:

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

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 baavgai

• Dreaming Coder

Reputation: 7153
• Posts: 14,897
• Joined: 16-October 07

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

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 ethereal1m

Reputation: 3
• Posts: 227
• Joined: 30-June 09

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

Reputation: 0
• Posts: 1
• Joined: 02-November 09

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

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 eDxOn007

Reputation: 0
• Posts: 1
• Joined: 30-January 12

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

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.