tree traversal: Inorder traversal sequence

I need a help to understand the algorithm

Page 1 of 1

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

#1 ethereal1m  Icon User is offline

  • D.I.C Head
  • member icon

Reputation: 3
  • View blog
  • Posts: 214
  • Joined: 30-June 09

tree traversal: Inorder traversal sequence

Post icon  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:
Posted Image

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
  • +

Replies To: tree traversal: Inorder traversal sequence

#2 Guest_Neumann*


Reputation:

Re: tree traversal: Inorder traversal sequence

Posted 26 September 2009 - 08:30 AM

View Postethereal1m, 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

Was This Post Helpful? 1

#3 baavgai  Icon User is offline

  • Dreaming Coder
  • member icon

Reputation: 5795
  • View blog
  • Posts: 12,628
  • Joined: 16-October 07

Re: tree traversal: Inorder traversal sequence

Posted 26 September 2009 - 09:19 AM

View Postethereal1m, 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.
Was This Post Helpful? 2
  • +
  • -

#4 ethereal1m  Icon User is offline

  • D.I.C Head
  • member icon

Reputation: 3
  • View blog
  • Posts: 214
  • 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.
Was This Post Helpful? 0
  • +
  • -

#5 rudreshwar  Icon User is offline

  • New D.I.C Head

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

Re: tree traversal: Inorder traversal sequence

Posted 03 November 2009 - 07:11 PM

View Postbaavgai, on 26 Sep, 2009 - 08:19 AM, said:

View Postethereal1m, 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.

Was This Post Helpful? 0
  • +
  • -

#6 eDxOn007  Icon User is offline

  • New D.I.C Head

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

Re: tree traversal: Inorder traversal sequence

Posted 30 January 2012 - 11:04 PM

View Postbaavgai, on 26 September 2009 - 09:19 AM, said:

View Postethereal1m, 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.

Was This Post Helpful? 0
  • +
  • -

Page 1 of 1