Solved

iterative inOrder printing a tree

Posted on 2004-03-25
13
3,891 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
Does Powershell have you tied up in knots?

Managing Active Directory does not always have to be complicated.  If you are spending more time trying instead of doing, then it's time to look at something else. For nearly 20 years, AD admins around the world have used one tool for day-to-day AD management: Hyena. Discover why

 
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

Is Your AD Toolbox Looking More Like a Toybox?

Managing Active Directory can get complicated.  Often, the native tools for managing AD are just not up to the task.  The largest Active Directory installations in the world have relied on one tool to manage their day-to-day administration tasks: Hyena. Start your trial today.

Question has a verified solution.

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

Suggested Solutions

Title # Comments Views Activity
Application launch issue with Apache Tomcat 5 45
splitOdd10 challenge 5 108
allswap challenge 6 99
Java string replace 11 48
For customizing the look of your lightweight component and making it look opaque like it was made of plastic.  This tip assumes your component to be of rectangular shape and completely opaque.   (CODE)
Java functions are among the best things for programmers to work with as Java sites can be very easy to read and prepare. Java especially simplifies many processes in the coding industry as it helps integrate many forms of technology and different d…
Viewers will learn about the different types of variables in Java and how to declare them. Decide the type of variable desired: Put the keyword corresponding to the type of variable in front of the variable name: Use the equal sign to assign a v…
This tutorial covers a step-by-step guide to install VisualVM launcher in eclipse.

821 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