Binary Tree Preorder Traverse

Hi,

I have the function below:

public void showStructure(AccountNode current, int offset, int step) {
    if ((current == null))
        return;
    showStructure(current.right, offset, step);            
   System.out.println(Integer.toString(++i) + " " + Pad.leftJustify("", offset) + current.accountName);
   showStructure(current.left, offset + step, step);            
}

It is supposed to display items in a tree in preorder traverse. I also want to store the items in an arrayList according to the order displayed.

Can someone please provide some pointers or show me how it can be done?

Thank you.

Regards
yiyi83Asked:
Who is Participating?
I wear a lot of hats...

"The solutions and answers provided on Experts Exchange have been extremely helpful to me over the last few years. I wear a lot of hats - Developer, Database Administrator, Help Desk, etc., so I know a lot of things but not a lot about one thing. Experts Exchange gives me answers from people who do know a lot about one thing, in a easy to use platform." -Todd S.

CEHJCommented:
You should recurse left before right
0
CEHJCommented:
You can add the current node to a List that's an instance variable

if ((current == null))
        return;
nodesVisited.add(current);
0
hoomanvCommented:
pre-order (prefix) traversal

visit(node)
    print node.value
    if node.left  != null then visit(node.left)
    if node.right != null then visit(node.right)
0
Cloud Class® Course: Microsoft Windows 7 Basic

This introductory course to Windows 7 environment will teach you about working with the Windows operating system. You will learn about basic functions including start menu; the desktop; managing files, folders, and libraries.

objectsCommented:
public void showStructure(AccountNode current, int offset, int step) {
    if ((current == null))
        return;
   System.out.println(Integer.toString(++i) + " " + Pad.leftJustify("", offset) + current.accountName);
    showStructure(current.right, offset, step);          
   showStructure(current.left, offset + step, step);          
}
0
hoomanvCommented:
the one you wrote is in-order (infix) traversal

    if node.left  != null then visit(node.left)
    print node.value
    if node.right != null then visit(node.right)
0
yiyi83Author Commented:
Dear All,

Thanks for the comments. I realize that I been using the wrong tranverse (Thanks to hoomany for highlighting).

How about the below?

private void preorderStore(AccountNode root) {
   if ( root != null ) {  // (Otherwise, there's nothing to print.)
       System.out.println(root.accountName);
       if (root.left != null) {
           preorderStore( root.left );   // Print items in left subtree.
       }
       if (root.right != null) {
           preorderStore( root.right );  // Print items in right subtree.
       }
    }
}

When I tried to store the value, it is looping.

Example:
Account One
Account One
Account Two
Account One
Account Two
Account Two.One

How can I eliminate the looping?

Regards
0
CEHJCommented:
Please post code where you add nodes
0
objectsCommented:
you don't need to check if right/left are null, as you check wheteher root is null already when called
And add the node the same place you print it out
, you can pass the node list as a parameter


private void preorderStore(List nodeList, AccountNode root) {
   if ( root != null ) {  // (Otherwise, there's nothing to print.)
       System.out.println(root.accountName);
       nodeList.add(root.accountName);
       preorderStore( nodeList, root.left );   // Print items in left subtree.
       preorderStore( nodeList, root.right );  // Print items in right subtree.
    }
}
0
yiyi83Author Commented:
The code as below:

private void preorderStore(AccountNode root) {
   if ( root != null ) {  // (Otherwise, there's nothing to print.)
       parentArray.add(root.accountName);
       System.out.println(root.accountName);
       if (root.left != null) {
           preorderStore( root.left );   // Print items in left subtree.
       }
       if (root.right != null) {
           preorderStore( root.right );  // Print items in right subtree.
       }
    }
}

Regards
0
CEHJCommented:
>>you don't need to check if right/left are null, as you check wheteher root is null already when called

Just because root != null, it doesn't mean root.left and root.right are not null. In fact, not checking is merely wasteful of the stack
0
CEHJCommented:
>>The code as below:

No, sorry - i should have been more explicit - i meant the code where you add the nodes to the tree in the first place
0
yiyi83Author Commented:
Hi CEHJ,

As below:

private void addAccount(AccountNode current, T accountName, T parentAccount) {
    if (parentAccount == null)
    {
        current = new AccountNode(accountName, null, null);
        current.right = root;
        root = current;
    } else {
         AccountNode parentNode;
         AccountNode temp;
         parentNode = find(parentAccount);
         if (parentNode == null)
          {
      System.out.println("Parent Node does not exist.");
      System.out.println(parentAccount);
          }
         if (parentNode.left == null)
         {
      temp = new AccountNode(accountName, null, null);
      parentNode.left = temp;
         } else {
      temp = new AccountNode(accountName, null, null);
      temp.right = parentNode.left;
      parentNode.left = temp;
         }
      }
}

Does this help?

Regards
0
hoomanvCommented:
what does it mean. what it is supposed to do
current.right = root;
root = current;
where the variable "root" is defined and of what type
0
hoomanvCommented:
i think you are creating a cycle
0
CEHJCommented:
It may help for debugging if you actually name the root 'Root' for now
0
yiyi83Author Commented:
Hi,

Basically, I am trying to create a tree structure such as below:

Account One
     Account One.One
          Account.One.One
          Account One.Two
     Account One.Two
     Account One.Three
Account Two
    Account Two.One
    Account Two.Two
         Account Two.Two.One
Account Three

When I add account two, it should be the right child of account one and so fro.
When I add account two.one, it should be the left child of account two and so fro.
When I add account two.two, it should be the left child of account two and two.one will be its right child.

Does my code achieve that? From my testing, it seem to do so. I will be glad to send my code out for more comments.

Please let me know. Thank you.

Regards
0
CEHJCommented:
>>new AccountNode(accountName, null, null);

What are the two last parameters to that ctor btw?
0
yiyi83Author Commented:
Hi CEHJ,

It is the left and right node.

As below:

public AccountNode(T newAccountName, AccountNode left, AccountNode right) {
    accountName = newAccountName;
    this.left = left;
    this.right = right;
}

Regards
0
CEHJCommented:
Another question: what kind of ordering is being used and how does it work?
0
yiyi83Author Commented:
Hi,

I am not sure of what u mean. If you are refering to how a new node is added, it is as below:

the user will indicate the parent account and input the new account name.
I will find the parent node and insert the new account node as the first child.

Regards
0
hoomanvCommented:
another pitfall (seperate from your program logic) that can cause a NullPointerException

         if (parentNode == null)
          {
 ////////////////
          }
         if (parentNode.left == null) // this should be "else if" other wise after getting out of first if an EXC will be thrown
         {
//////////////////
         }
         else {
///////////////
         }
0
CEHJCommented:
>>I am not sure of what u mean.

Some binary trees are ordered, some are not. Is one node 'greater' than another in your case?
0
yiyi83Author Commented:
Hi CEHJ,

My binary tree is based on user indication.

For example:

I have 3 top nodes, N1, N2, N3. Right child of N1 is N2. Right child of N2 is N3.

if user indicate, parent = N1
new node name = N1.1

The node, N1.1 will be the left child of N1.

Is that clearer?
0
yiyi83Author Commented:
Hi All,

I resolved my problem by initiatising the array at the start of the call.

Thank you all for helping.

Regards
0
GranModCommented:
Closed, 100 points refunded.
GranMod
The Experts Exchange
Community Support Moderator of all Ages
0

Experts Exchange Solution brought to you by

Your issues matter to us.

Facing a tech roadblock? Get the help and guidance you need from experienced professionals who care. Ask your question anytime, anywhere, with no hassle.

Start your 7-day free trial
It's more than this solution.Get answers and train to solve all your tech problems - anytime, anywhere.Try it for free Edge Out The Competitionfor your dream job with proven skills and certifications.Get started today Stand Outas the employee with proven skills.Start learning today for free Move Your Career Forwardwith certification training in the latest technologies.Start your trial today
Java

From novice to tech pro — start learning today.

Question has a verified solution.

Are you are experiencing a similar issue? Get a personalized answer when you ask a related question.

Have a better answer? Share it in a comment.