Binary Tree Preorder Traverse

You should recurse left before right

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

if ((current == null))
        return;
nodesVisited.add(current);

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)

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);          
}

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)

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

Please post code where you add nodes

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

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

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

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

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

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

i think you are creating a cycle

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

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

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

What are the two last parameters to that ctor btw?

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

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

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

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 {
///////////////
         }

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

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?

Hi All,

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

Thank you all for helping.

Regards