We help IT Professionals succeed at work.

Binary Tree Preorder Traverse

yiyi83
yiyi83 asked
on
Medium Priority
282 Views
Last Modified: 2008-02-01
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
Comment
Watch Question

CERTIFIED EXPERT
Top Expert 2016

Commented:
You should recurse left before right
CERTIFIED EXPERT
Top Expert 2016

Commented:
You can add the current node to a List that's an instance variable

if ((current == null))
        return;
nodesVisited.add(current);
Top Expert 2006

Commented:
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)
Mick BarryJava Developer
CERTIFIED EXPERT
Top Expert 2010

Commented:
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);          
}
Top Expert 2006

Commented:
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)

Author

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
CERTIFIED EXPERT
Top Expert 2016

Commented:
Please post code where you add nodes
Mick BarryJava Developer
CERTIFIED EXPERT
Top Expert 2010

Commented:
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.
    }
}

Author

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
CERTIFIED EXPERT
Top Expert 2016

Commented:
>>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
CERTIFIED EXPERT
Top Expert 2016

Commented:
>>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

Author

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
Top Expert 2006

Commented:
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
Top Expert 2006

Commented:
i think you are creating a cycle
CERTIFIED EXPERT
Top Expert 2016

Commented:
It may help for debugging if you actually name the root 'Root' for now

Author

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
CERTIFIED EXPERT
Top Expert 2016

Commented:
>>new AccountNode(accountName, null, null);

What are the two last parameters to that ctor btw?

Author

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
CERTIFIED EXPERT
Top Expert 2016

Commented:
Another question: what kind of ordering is being used and how does it work?

Author

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
Top Expert 2006

Commented:
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 {
///////////////
         }
CERTIFIED EXPERT
Top Expert 2016

Commented:
>>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?

Author

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?

Author

Commented:
Hi All,

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

Thank you all for helping.

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

Not the solution you were looking for? Getting a personalized solution is easy.

Ask the Experts
Access more of Experts Exchange with a free account
Thanks for using Experts Exchange.

Create a free account to continue.

Limited access with a free account allows you to:

  • View three pieces of content (articles, solutions, posts, and videos)
  • Ask the experts questions (counted toward content limit)
  • Customize your dashboard and profile

*This site is protected by reCAPTCHA and the Google Privacy Policy and Terms of Service apply.

OR

Please enter a first name

Please enter a last name

8+ characters (letters, numbers, and a symbol)

By clicking, you agree to the Terms of Use and Privacy Policy.