Solved

iterative inOrder printing a tree

Posted on 2004-03-25
13
3,889 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
  • 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
 
LVL 30

Expert Comment

by:mayankeagle
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:mayankeagle
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
Highfive + Dolby Voice = No More Audio Complaints!

Poor audio quality is one of the top reasons people don’t use video conferencing. Get the crispest, clearest audio powered by Dolby Voice in every meeting. Highfive and Dolby Voice deliver the best video conferencing and audio experience for every meeting and every room.

 
LVL 30

Accepted Solution

by:
mayankeagle 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:mayankeagle
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:mayankeagle
ID: 10694477
Ok, compscigirl, now you can choose the correct answer and assists.
0

Featured Post

How your wiki can always stay up-to-date

Quip doubles as a “living” wiki and a project management tool that evolves with your organization. As you finish projects in Quip, the work remains, easily accessible to all team members, new and old.
- Increase transparency
- Onboard new hires faster
- Access from mobile/offline

Join & Write a Comment

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…
This was posted to the Netbeans forum a Feb, 2010 and I also sent it to Verisign. Who didn't help much in my struggles to get my application signed. ------------------------- Start The idea here is to target your cell phones with the correct…
Viewers will learn about if statements in Java and their use The if statement: The condition required to create an if statement: Variations of if statements: An example using if statements:
Viewers will learn how to properly install Eclipse with the necessary JDK, and will take a look at an introductory Java program. Download Eclipse installation zip file: Extract files from zip file: Download and install JDK 8: Open Eclipse and …

757 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

Need Help in Real-Time?

Connect with top rated Experts

17 Experts available now in Live!

Get 1:1 Help Now