File APIs for Java Developers
Manipulate DOC, XLS, PPT, PDF and many others from your application.
The moose likes Beginning Java and the fly likes Binary trees problem Big Moose Saloon
  Search | Java FAQ | Recent Topics | Flagged Topics | Hot Topics | Zero Replies
Register / Login
JavaRanch » Java Forums » Java » Beginning Java
Bookmark "Binary trees problem" Watch "Binary trees problem" New topic

Binary trees problem

Johan Mena

Joined: Nov 10, 2011
Posts: 11
So this is a problem in my assignment: Start with the and modify it to create a binary tree from a string of letters (like A, B, and so on) entered by the user. Each letter will be displayed in its own node. Construct the tree so that all the nodes that contain letters are leaves. Parent nodes can contain some non-letter symbol like +. Make sure that every parent node has exactly two children. Don’t worry if the tree is unbalanced. Note that this will not be a search tree; there’s no quick way to find a given node. You may end up with something like this:

One way to begin is by making an array of trees. (A group of unconnected trees is called a forest.) Take each letter typed by the user and put it in a node. Take each of these nodes and put it in a tree, where it will be the root. Now put all these one-node trees in the array. Start by making a new tree with + at the root and two of the one-node trees as its children. Then keep adding one-node trees from the array to this larger tree. Don’t worry if it’s an unbalanced tree. You can actually store this intermediate tree in the array by writing over a cell whose contents have already been added to the tree.

This is the code I have so far:

I'm having trouble following the instructions for some reason. I changed the node instance variable in Tree from private to public so that I can assign new nodes directly. My problem is when I get to the "Then keep adding one-node trees from the array to this larger tree." part. It just doesn't make sense. My reasoning is that I have to add a tree of the form: root: '+', leftChild: '+', rightChild: 'one-node Tree' (see graphic). But how do I add this to the top of 'hugeTree'?

Also, when I run the code I input the first letter, but it immediately gives a null pointer exception on line 100:

For some reason my brain is not processing all of this correctly. :/
Winston Gutkowski

Joined: Mar 17, 2011
Posts: 8942

I split a few of your long comment lines. When they're inside code blocks they tend to screw up the windowing.


Bats fly at night, 'cause they aren't we. And if we tried, we'd hit a tree -- Ogden Nash (or should've been).
Articles by Winston can be found here
I agree. Here's the link:
subject: Binary trees problem
It's not a secret anymore!