Quantcast

Maximum PC

It is currently Thu Sep 18, 2014 7:02 am

All times are UTC - 8 hours




Post new topic Reply to topic  [ 7 posts ] 
Author Message
 Post subject: Help with understanding traversal of a binary tree
PostPosted: Tue Oct 18, 2011 8:17 pm 
8086
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 :lol:). 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
  Profile  
 
 Post subject: Re: Help with understanding traversal of a binary tree
PostPosted: Tue Oct 18, 2011 8:31 pm 
Thoroughbred
Thoroughbred
User avatar

Joined: Sat May 07, 2011 12:30 pm
Posts: 1922
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
  Profile  
 
 Post subject: Re: Help with understanding traversal of a binary tree
PostPosted: Wed Oct 19, 2011 2:14 pm 
Java Junkie
Java Junkie
User avatar

Joined: Mon Jun 14, 2004 10:23 am
Posts: 24224
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 :lol:). 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
  Profile  
 
 Post subject: Re: Help with understanding traversal of a binary tree
PostPosted: Wed Oct 19, 2011 2:39 pm 
Thoroughbred
Thoroughbred
User avatar

Joined: Sat May 07, 2011 12:30 pm
Posts: 1922
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
  Profile  
 
 Post subject: Re: Help with understanding traversal of a binary tree
PostPosted: Wed Oct 19, 2011 4:04 pm 
Java Junkie
Java Junkie
User avatar

Joined: Mon Jun 14, 2004 10:23 am
Posts: 24224
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. :P


Top
  Profile  
 
 Post subject: Re: Help with understanding traversal of a binary tree
PostPosted: Wed Oct 19, 2011 4:07 pm 
Thoroughbred
Thoroughbred
User avatar

Joined: Sat May 07, 2011 12:30 pm
Posts: 1922
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
  Profile  
 
 Post subject: Re: Help with understanding traversal of a binary tree
PostPosted: Fri Oct 21, 2011 12:35 pm 
Java Junkie
Java Junkie
User avatar

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


Top
  Profile  
 
Display posts from previous:  Sort by  
Post new topic Reply to topic  [ 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 forum
You cannot reply to topics in this forum
You cannot edit your posts in this forum
You cannot delete your posts in this forum
You cannot post attachments in this forum

Search for:
Jump to:  
Powered by phpBB © 2000, 2002, 2005, 2007 phpBB Group