Solved

iterative inOrder printing a tree

Posted on 2004-03-25
13
3,893 Views
Last Modified: 2007-12-19
hii, i'm doing a program that's supposed to printOut a tree using iterative inOrder and with a self created Stack.

so i created a ListStack

class ListStack
{
      private java.util.LinkedList list;
      
      public ListStack()
      {
            list = new java.util.LinkedList();
      }
      
      public boolean isEmpty()
      {
            return list.isEmpty();
      }
      
      public void push(Object obj)
      {
            list.addFirst(obj);
      }
      
      public Object pop()
      {
            return list.removeFirst();
      }
      
      public Object peakTop()
      {
            return list.getFirst();
      }
}


and although i followed the outline to write my inorder, it gives NullPointerException error.
can anyone please show me what i did wrong. thnx very much.

    public void printInOrder(TreeNode root)
    {
            ListStack s = new ListStack();
            TreeNode temp = root;
            do
            {
                  while(temp != null)
                  {                  
                        s.push(temp.getValue());
                        temp = temp.getLeft();                        
                  }
                  
                  if(!(s.isEmpty()))
                  {                  
                        s.pop();
                  }            
                  System.out.println(temp.getValue());      
                  temp = temp.getRight();
            }
            while( (temp != null) || (! (s.isEmpty()) ) );
    }
0
Comment
Question by:compscigirl
[X]
Welcome to Experts Exchange

Add your voice to the tech community where 5M+ people just like you are talking about what matters.

  • Help others & share knowledge
  • Earn cash & points
  • Learn & ask questions
  • 5
  • 5
  • 2
13 Comments
 
LVL 5

Assisted Solution

by:twobitadder
twobitadder earned 20 total points
ID: 10683984
I can tell you why you have a null pointer exception but I've never attempted iterative in-order traversal of a tree.

You get the null pointer because you fly down the left of the tree until you cannot go any further, then here:

System.out.println(temp.getValue());    
               temp = temp.getRight();

you try to get the right child of the smallest element in the tree, this may or may not exists:

picture might help:
         /                                               /
        ^                                              ^
   smallest                                     smallest
  ^         ^                                     ^      ^       <----no right child.
          2ndsmallest
0
 
LVL 5

Expert Comment

by:twobitadder
ID: 10684014
You need to move down the left side pushing all the nodes onto the stack, then when you hit the smallest(no more left children) you pop smallest off the top of stack and print it, test it for a right child.
  If it has one, push that child onto stack and try run down its left side, then again, you pop them back off, printing  and checking for right subtrees after you print each node.  If it doesn't have a right child pop the next off the stack, print it and check for right child.

This logic works but you'll need to form it into loops.
0
 

Author Comment

by:compscigirl
ID: 10684164
hi, is there anyway i can fix my original code to follow the peudocode like this

void inorder (TreeNode root)
{
  declare a stack of TreeNode, initialized as empty
  declare temp as a TreeNode
 
  start temp = root

  do
  {
    while moving temp as far left as possible,
      push tree references onto the stack

    if the stack is not empty
      reposition temp by popping the stack

    print the contents of tempgetValue()
    move temp one node to the right
  }
  while (the stack is not empty) or (temp != null)
}


thanks
0
Technology Partners: We Want Your Opinion!

We value your feedback.

Take our survey and automatically be enter to win anyone of the following:
Yeti Cooler, Amazon eGift Card, and Movie eGift Card!

 
LVL 30

Expert Comment

by:Mayank S
ID: 10684366
void inorder ( TreeNode root )
{
  Stack stack = new Stack () ;
  NodeTree temp = root ;

  if ( temp == null )
    return ;

  do
  {
    while ( temp != null )
    {
      stack.push ( temp ) ;
      temp = temp.getLeft () ;

    } // end while

  if ( ! stack.empty () )
    temp = ( TreeNode ) stack.pop () ; // end if

  if ( temp != null )
  {
    System.out.println ( temp.getValue () ) ;
    temp = temp.getRight () ;

  } // end if

 } while ( ! stack.empty () || temp != null ) ; // end do-while

} // end of inorder ()
0
 
LVL 30

Expert Comment

by:Mayank S
ID: 10684370
I didn't run that code, but I hope that you can understand what mistakes you made.
0
 

Author Comment

by:compscigirl
ID: 10684448
oh haaha. i figured out.
thanks a lot. it was a dumb mistake. when i print out the getValue. I shouldn't have added the (TreeNode)....

thnx guys
0
 
LVL 30

Accepted Solution

by:
Mayank S earned 50 total points
ID: 10684465
Can we have it closed now? Your mistakes were:

1. Printing:
>> System.out.println(temp.getValue());    
>> temp = temp.getRight();

- without checking if 'temp' is null.

2. Pushing value:

>> s.push(temp.getValue());

- instead of 'temp' itself. Should've been: s.push ( temp ) ;

3. Popping anonymously: >>  s.pop();

Should've been: temp = ( TreeNode ) s.pop () ;

I hope you noticed those changes in my code.
0
 

Author Comment

by:compscigirl
ID: 10684482
ya i did notice.
but is it necessary to have the checking if 'temp' is null before print?
0
 

Author Comment

by:compscigirl
ID: 10684488
since it's already checking before pop.
0
 

Author Comment

by:compscigirl
ID: 10684524
oops. clicked the wrong accepted answer............
0
 
LVL 30

Expert Comment

by:Mayank S
ID: 10684628
>> clicked the wrong accepted answer

You can post a 0-point question in Community Support http://www.experts-exchange.com/Community_Support/ and ask them to re-open the question for you so that you can change the accepted answer.

>> but is it necessary to have the checking if 'temp' is null before print

Yes, because the value of temp might change with temp = temp.getLeft () ; and when it is null, it will come out of the while ( temp != null ) loop. So it means that temp is null outside this loop. Now if the stack is not empty, then a value will be popped from the stack and temp will start referring to it, otherwise, temp will be null -> so you should check if temp is null or not.

Mayank.
0
 
LVL 30

Expert Comment

by:Mayank S
ID: 10694477
Ok, compscigirl, now you can choose the correct answer and assists.
0

Featured Post

Salesforce Made Easy to Use

On-screen guidance at the moment of need enables you & your employees to focus on the core, you can now boost your adoption rates swiftly and simply with one easy tool.

Question has a verified solution.

If you are experiencing a similar issue, please ask a related question

Suggested Solutions

Title # Comments Views Activity
Maven Project: Hibernate Dependencies Conflict 10 54
Way to decrease size of apk file 9 112
ejb wildfly example 2 75
Java: anonymous class 4 39
An old method to applying the Singleton pattern in your Java code is to check if a static instance, defined in the same class that needs to be instantiated once and only once, is null and then create a new instance; otherwise, the pre-existing insta…
Java contains several comparison operators (e.g., <, <=, >, >=, ==, !=) that allow you to compare primitive values. However, these operators cannot be used to compare the contents of objects. Interface Comparable is used to allow objects of a cl…
Viewers learn about the third conditional statement “else if” and use it in an example program. Then additional information about conditional statements is provided, covering the topic thoroughly. Viewers learn about the third conditional statement …
Viewers learn about the scanner class in this video and are introduced to receiving user input for their programs. Additionally, objects, conditional statements, and loops are used to help reinforce the concepts. Introduce Scanner class: Importing…

730 members asked questions and received personalized solutions in the past 7 days.

Join the community of 500,000 technology professionals and ask your questions.

Join & Ask a Question