# Maximum PC

 It is currently Tue May 05, 2015 8:27 pm

 All times are UTC - 8 hours

 Page 1 of 1 [ 7 posts ]
 Print view Previous topic | Next topic
Author Message
 Post subject: Help with understanding traversal of a binary treePosted: Tue Oct 18, 2011 8:17 pm
 8086

Joined: Wed Feb 03, 2010 7:05 pm
Posts: 5
We've just finished going over binary trees in my computer science class and I understand most of it (conceptually, implementing a binary tree may be a different story ). However, I do not fully understand exactly how a traversal works recursively.

My teacher provided this pseudo-code for explaining traversal:
Code:
traverse(treenode *root) (root is the root of a subtree, not the tree)
if root is NOT null (base case - nothing to do if it is NULL)
traverse(root->left)
do something with root
traverse(root->right)

What I'm trying to figure out is how it hits every single node in the binary tree with this recursive call. I can see that it would head to the left, recursively, but at what point in the traversal algorithm does it stop going to the left and start going right from the sub-tree's root?

Top

 Post subject: Re: Help with understanding traversal of a binary treePosted: Tue Oct 18, 2011 8:31 pm
 Thoroughbred

Joined: Sat May 07, 2011 12:30 pm
Posts: 1963
Location: A place not actively occupied by something else.
We start with the furthest item to the right and head left. When we reach the end, the program does something to the sub-tree root and heads to the right.
Read this: Wikipedia on Traversal
Your teacher's example is the first under this heading.
Think of it in a DOS prompt:
Code:
C:>dir
.. Programs Users  Windows

So, ".." is the root of the sub-tree C. To traverse, we go to the right and look at Programs, then Users, then Windows. In a binary tree, you have stuff on both sides of the root, so we first go to the left of the root, then do the action. Next, we go to the root, and scan to the right.

Top

 Post subject: Re: Help with understanding traversal of a binary treePosted: Wed Oct 19, 2011 2:14 pm
 Java Junkie

Joined: Mon Jun 14, 2004 10:23 am
Posts: 24245
Location: Granite Heaven
tardisromana wrote:
We've just finished going over binary trees in my computer science class and I understand most of it (conceptually, implementing a binary tree may be a different story ). However, I do not fully understand exactly how a traversal works recursively.

My teacher provided this pseudo-code for explaining traversal:
Code:
traverse(treenode *root) (root is the root of a subtree, not the tree)
if root is NOT null (base case - nothing to do if it is NULL)
traverse(root->left)
do something with root
traverse(root->right)

What I'm trying to figure out is how it hits every single node in the binary tree with this recursive call. I can see that it would head to the left, recursively, but at what point in the traversal algorithm does it stop going to the left and start going right from the sub-tree's root?

It helps if you draw a tree and work through it using the recursive algorithm.

Imagine a tree with 3 levels. The first level has only the root (0) . The second level has two nodes (1 and 2) . The third level has four (3, 4, 5 and 6).

0
1 2
3 4 5 6

(sorry .. this diagram isn't working well .. these should be spaced out in a pyramid. 0 branches to 1 and 2 ... 1 branches to 3 and 4 ... 2 branches to 5 and 6)

Start at the root:
traverse ( 0 )
root is not null, so we traverse (root -> left) to 1.
1 is not null, so we traverse (1 -> left) to 3.
3 is not null, so we traverse (3 -> left) to null.
null is null, so we do nothing and return.
do something with 3
traverse (3 -> right) to null.
null is null so we do nothing and return.
do something with 1
traverse (1 -> right) to 4
4 is not null, so we traverse (4 -> left) to null
null is null, so we do nothing and return.
do something with 4
traverse (4 -> right) to null.
null is null so we do nothing and return.

... and so on.

Does that make sense?

Quote:
We start with the furthest item to the right and head left. When we reach the end, the program does something to the sub-tree root and heads to the right.

He understands traversals. He is having difficulty with recursion.

Top

 Post subject: Re: Help with understanding traversal of a binary treePosted: Wed Oct 19, 2011 2:39 pm
 Thoroughbred

Joined: Sat May 07, 2011 12:30 pm
Posts: 1963
Location: A place not actively occupied by something else.
Still, pretty good considering the programming class I had only spent 10 minutes on the subject.

Top

 Post subject: Re: Help with understanding traversal of a binary treePosted: Wed Oct 19, 2011 4:04 pm
 Java Junkie

Joined: Mon Jun 14, 2004 10:23 am
Posts: 24245
Location: Granite Heaven
noghiri_x wrote:
Still, pretty good considering the programming class I had only spent 10 minutes on the subject.

Well, no, because you just paraphrased the wiki entry rather than addressing his question.

Top

 Post subject: Re: Help with understanding traversal of a binary treePosted: Wed Oct 19, 2011 4:07 pm
 Thoroughbred

Joined: Sat May 07, 2011 12:30 pm
Posts: 1963
Location: A place not actively occupied by something else.
I wrote the thing before I looked up on Wikipedia to double check. I then incorporated the link.

Top

 Post subject: Re: Help with understanding traversal of a binary treePosted: Fri Oct 21, 2011 12:35 pm
 Java Junkie

Joined: Mon Jun 14, 2004 10:23 am
Posts: 24245
Location: Granite Heaven
Well, he hasn't come back here so I guess the point is moot.

Top

 Display posts from previous: All posts1 day7 days2 weeks1 month3 months6 months1 year Sort by AuthorPost timeSubject AscendingDescending
 Page 1 of 1 [ 7 posts ]

 All times are UTC - 8 hours

#### Who is online

Users browsing this forum: No registered users and 3 guests

 You cannot post new topics in this forumYou cannot reply to topics in this forumYou cannot edit your posts in this forumYou cannot delete your posts in this forumYou cannot post attachments in this forum

Search for:
 Jump to:  Select a forum ------------------ Maximum FAQs    Forum Rules, Posting Guidelines & Announcements    The Good, The Bad & The Banned    FAQs Help/Do It Yourself    PC Building Lab    The Help Desk    PC Modding    Education & Certification Hardware    Nuts & Bolts    Portable Talk    Appraisals, Deals & Bargains (oh my!) OS/Software/Programming    Windows Parlor    Alt.OS.Abode    Games Arena    Programmers' Paradise Networking/Internet    Internet Truckstop    Network Nook In/Out    Magazine and Book Feedback    Forum & Website Feedback    Dog Pound Team Maximum PC Folding at Home    Team Maximum PC - Folding at Home - FIND CURES TO DISEASES    Team MPC - Folding Gauntlets
Powered by phpBB © 2000, 2002, 2005, 2007 phpBB Group