Greetings experts,
I need help to get a grip on understanding of binary tree in inorder transversal.
according to wiki:
To traverse a nonempty 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  7594 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
