Solved

iterative inOrder printing a tree

Posted on 2004-03-25
13
3,894 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
Get 15 Days FREE Full-Featured Trial

Benefit from a mission critical IT monitoring with Monitis Premium or get it FREE for your entry level monitoring needs.
-Over 200,000 users
-More than 300,000 websites monitored
-Used in 197 countries
-Recommended by 98% of users

 
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

Creating Instructional Tutorials  

For Any Use & On Any Platform

Contextual Guidance at the moment of need helps your employees/users adopt software o& achieve even the most complex tasks instantly. Boost knowledge retention, software adoption & employee engagement with easy solution.

Question has a verified solution.

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

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…
Basic understanding on "OO- Object Orientation" is needed for designing a logical solution to solve a problem. Basic OOAD is a prerequisite for a coder to ensure that they follow the basic design of OO. This would help developers to understand the b…
Viewers will learn about the regular for loop in Java and how to use it. Definition: Break the for loop down into 3 parts: Syntax when using for loops: Example using a for loop:
This theoretical tutorial explains exceptions, reasons for exceptions, different categories of exception and exception hierarchy.

724 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