• Post Reply Bookmark Topic Watch Topic
  • New Topic

Level Order Traversal  RSS feed

 
Ryan O'Neill
Ranch Hand
Posts: 86
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
We are working with LinkedBinarySearchTrees. One of specs on my assignment is to "Using a level-order traversal, create a 2-D display of your trees, using the forward and back slashes as the branch lines. The tree nodes should be spaced proportionally to show the structure of the tree neatly." I am not asking anyone to do the problem, but where do I start with a problem like this?
 
Junilu Lacar
Sheriff
Posts: 11477
180
Android Debian Eclipse IDE IntelliJ IDE Java Linux Mac Spring Ubuntu
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
You would need to start with the traversal algorithm and get that working first. Then you'd need to insert statements in the appropriate place to build up your display strings. You may be able to display as you traverse or you may choose to display after traversing and building up all the display strings.

See this thread: http://www.coderanch.com/t/647965/java/java/write-inorder-method-trees#2988207 for some ideas on how you would display on the fly. If you build display strings as you traverse, then display after full traversal is complete, then you'd replace the System.out.println() statements with String concatenation operations.
 
Ryan O'Neill
Ranch Hand
Posts: 86
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
How does a level order traversal work?
 
Junilu Lacar
Sheriff
Posts: 11477
180
Android Debian Eclipse IDE IntelliJ IDE Java Linux Mac Spring Ubuntu
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
Traverse and gather display data, then display is probably the best way to go for this, especially since there's a requirement to "show the structure of the tree neatly" which means spacing should be proportionate and the branch lines are aligned so they are pointing at your node data. Calculating spacing can get tricky so it's best to separate this concern from the other concern of traversing the tree. Mixing these two concerns in your program code is just inviting in bugs and a lot of confusion and headaches.
 
Junilu Lacar
Sheriff
Posts: 11477
180
Android Debian Eclipse IDE IntelliJ IDE Java Linux Mac Spring Ubuntu
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
My plan of attack would be something like this:

1. Traverse the tree
2. As I traverse the tree and output a node, gather data for display
3. After traversing the tree, given all the data I gathered, display that data

The challenge here is choosing the appropriate data structure to keep your display data as you traverse the tree. If you could determine the height and breadth of the tree, an array of arrays could work. Otherwise, a List of Lists is what I would try to use.

Caveat: these are all just ideas off the top of my head. I haven't tried to implement a solution myself to see how well these ideas will work out, if at all.
 
Junilu Lacar
Sheriff
Posts: 11477
180
Android Debian Eclipse IDE IntelliJ IDE Java Linux Mac Spring Ubuntu
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
Ryan O'Neill wrote:How does a level order traversal work?


Do you not have that in your class notes? If not, then have you tried searching around? Google is your friend.
 
Ryan O'Neill
Ranch Hand
Posts: 86
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
I have been searching Google lol. I just haven't found one that will work.
 
Junilu Lacar
Sheriff
Posts: 11477
180
Android Debian Eclipse IDE IntelliJ IDE Java Linux Mac Spring Ubuntu
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
Ryan O'Neill wrote:I have been searching Google lol. I just haven't found one that will work.

Really? This search seems to turn up some good links: level order traversal
 
Ryan O'Neill
Ranch Hand
Posts: 86
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
Yeah I have seen those but they are totally different from what I need.
 
Junilu Lacar
Sheriff
Posts: 11477
180
Android Debian Eclipse IDE IntelliJ IDE Java Linux Mac Spring Ubuntu
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
Ryan O'Neill wrote:Yeah I have seen those but they are totally different from what I need.

How so? I would think that the general algorithm for the BFS would be a great starting point. What exactly is it that you think you need that makes any/all of the information you can find at those links unsuited for your purposes?
 
Ryan O'Neill
Ranch Hand
Posts: 86
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
Well this is close but I am not using a queue and I don't know what to do.

 
Stefan Evans
Bartender
Posts: 1837
10
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
(Scratches head)
Why if you are not using a queue, are you using a variable CALLED queue?
What defines a queue anyway? The object you have or the use you put it to?
Or is this bit of code you posted unrelated to your actual code? (head asplodes)


I would suggest starting simply.
Print out the nodes in the correct WITHOUT worrying about any special formatting.
 
Junilu Lacar
Sheriff
Posts: 11477
180
Android Debian Eclipse IDE IntelliJ IDE Java Linux Mac Spring Ubuntu
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
Ryan O'Neill wrote:Well this is close but I am not using a queue and I don't know what to do.

Well, sorry to say this, but you're going to have to pull that thinking cap down tighter and start understanding the general principle behind what that code is doing and see what you can apply from there to the specific objects that you're using. I doubt you'll find anything out there that's specific to the LinkedBinarySearchTree class you mentioned in your other post, unless someone else who has gone through the same exercise has posted their solution online. We discourage wholesale copying of things like that though because it defeats the purpose of studying this stuff.

I personally think that this page: http://www.geeksforgeeks.org/level-order-tree-traversal/ actually has most of the information you need and if you understand the algorithms laid out there and you understand what your classes are doing or capable of doing, then you should be well on your way.

If you don't quite understand your LinkedBinarySearchTree class, then that's a big hurdle you have to get over first.

Good luck.
 
  • Post Reply Bookmark Topic Watch Topic
  • New Topic
Boost this thread!