School Assignment? Project Due Tomorrow? Chat LIVE With A Programming Expert!

Programming Help

Web Development



What's Here?

  • Members: 306,983
  • Replies: 841,428
  • Topics: 140,601
  • Snippets: 4,465
  • Tutorials: 1,166
  • Total Online: 1,957
  • Members: 98
  • Guests: 1,859

Welcome to Dream.In.Code
Become an Expert!

Join 306,983 Programmers for FREE! Get instant access to thousands of experts, tutorials, code snippets, and more! There are 1,957 people online right now. Registration is fast and FREE... Join Now!




tree traversal: Inorder traversal sequence

 

tree traversal: Inorder traversal sequence, I need a help to understand the algorithm
ethereal1m

26 Sep, 2009 - 01:22 AM
Post #1

D.I.C Head
**

Joined: 29 Jun, 2009
Posts: 76



Thanked: 1 times
My Contributions
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:
IPB 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







User is offlineProfile CardPM
+Quote Post


Neumann

RE: Tree Traversal: Inorder Traversal Sequence

26 Sep, 2009 - 07:30 AM
Post #2

I can judge a book by its cover
Group Icon

Joined: 8 Jul, 2009
Posts: 686



Thanked: 93 times
Dream Kudos: 225
My Contributions
QUOTE(ethereal1m @ 26 Sep, 2009 - 01:22 AM) *

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 Sep, 2009 - 07:31 AM
User is offlineProfile CardPM
+Quote Post

baavgai

RE: Tree Traversal: Inorder Traversal Sequence

26 Sep, 2009 - 08:19 AM
Post #3

Dreaming Coder
Group Icon

Joined: 16 Oct, 2007
Posts: 4,348



Thanked: 410 times
Dream Kudos: 550
Expert In: C, C++, Java, C#, ASP.NET, PHP, Perl, Python, Oracle, SQL Server, MySql, HTML, JavaScript, Lua, Cheese

My Contributions
QUOTE(ethereal1m @ 26 Sep, 2009 - 03:22 AM) *

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:
CODE

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.
User is online!Profile CardPM
+Quote Post

ethereal1m

RE: Tree Traversal: Inorder Traversal Sequence

27 Sep, 2009 - 12:10 AM
Post #4

D.I.C Head
**

Joined: 29 Jun, 2009
Posts: 76



Thanked: 1 times
My Contributions
OK, thanks guys for the replies. I didn't get a recursive notion properly. I do now.
User is offlineProfile CardPM
+Quote Post

rudreshwar

RE: Tree Traversal: Inorder Traversal Sequence

3 Nov, 2009 - 06:11 PM
Post #5

New D.I.C Head
*

Joined: 2 Nov, 2009
Posts: 1
QUOTE(baavgai @ 26 Sep, 2009 - 08:19 AM) *

QUOTE(ethereal1m @ 26 Sep, 2009 - 03:22 AM) *

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:
CODE

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.
User is offlineProfile CardPM
+Quote Post

Fast ReplyReply to this topicStart new topic

Time is now: 11/21/09 05:29AM
Invision Power Board v2.1.7 © 2009  IPS, Inc.
Licensed to: MediaGroup1

Live Help!

Be Social

Dream.In.Code RSS Feed Dream.In.Code LinkedIn Group Follow Us On Twitter Fan Us On Facebook

Tutorials

Programming

Web Development

Reference Sheets

Code Snippets

DIC Chatroom

Bye Bye Ads

Monthly Drawing

Thumb Drive

Top Contributors

Top 10 Kudos This Month