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
Solved

iterative inOrder printing a tree

Posted on 2004-03-25
13
3,892 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
Announcing the Most Valuable Experts of 2016

MVEs are more concerned with the satisfaction of those they help than with the considerable points they can earn. They are the types of people you feel privileged to call colleagues. Join us in honoring this amazing group of Experts.

 
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

Free Tool: SSL Checker

Scans your site and returns information about your SSL implementation and certificate. Helpful for debugging and validating your SSL configuration.

One of a set of tools we are providing to everyone as a way of saying thank you for being a part of the community.

Question has a verified solution.

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

Suggested Solutions

Title # Comments Views Activity
Why my table column Id is not passed to java object? 4 44
iterator/ListIterator approach 17 39
Chrome and Firefox Java 5 50
Java: anonymous class 4 29
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)
By the end of 1980s, object oriented programming using languages like C++, Simula69 and ObjectPascal gained momentum. It looked like programmers finally found the perfect language. C++ successfully combined the object oriented principles of Simula w…
Viewers will learn about arithmetic and Boolean expressions in Java and the logical operators used to create Boolean expressions. We will cover the symbols used for arithmetic expressions and define each logical operator and how to use them in Boole…
The viewer will learn how to implement Singleton Design Pattern in Java.

840 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