Threaded Tree Traversal

Dev Shed Forums Sponsor:

March 5th, 2013, 06:00 AM

Mr_Bean

Registered User

Join Date: Feb 2013

Posts: 6

Time spent in forums: 1 h 3 m 56 sec
Reputation Power: 0

Homework - Threaded Tree Traversal

Hello,

As an assignment we have to write a method for a Threaded Binary Tree that traverses the tree in post-order. However, we aren't allowed to use recursion or stacks

This is what I have so far (after doing some Googling):

java Code:

Original - java Code

public void postOrder() {
    ThreadedTreeNode<T> temp = new ThreadedTreeNode<T>(null);
    String action = "left";
    ArrayList<ThreadedTreeNode<T>> visited = new ArrayList<ThreadedTreeNode<T>>();
 
    temp.left = root;
    
    while (temp != null) {
        if (action == "left") {
            if (temp.left != null && !visited.contains(temp.left))
                temp = temp.left;
            else
                action = "right";
        }
        else if (action == "right") {
            if (temp.left != null && !visited.contains(temp.left))
                action = "left";
            else
                action = "visit";
        }
        else if (action == "visit") {
            visit(temp);
            visited.add(temp);
 
            if (temp.right.left == temp) {
                action = "right";
                temp = temp.right;  
            }
            
            if (temp.right == null)
                return;
        }
    }
}

Any ideas on what's wrong? It just goes into an infinite loop when visiting the root.

Thanks,

Mr_Bean

March 5th, 2013, 06:22 AM

NormR

Contributing User

Join Date: Aug 2010

Location: SW Missouri

Posts: 2,958

Time spent in forums: 1 Week 6 Days 3 h 7 m 10 sec
Reputation Power: 345

One problem is the use of == to compare Strings. The code should use the equals() method.

March 6th, 2013, 12:32 AM

Mr_Bean

Registered User

Join Date: Feb 2013

Posts: 6

Time spent in forums: 1 h 3 m 56 sec
Reputation Power: 0

Thanks, but that didn't solve the problem.

March 6th, 2013, 06:17 AM

NormR

Contributing User

Join Date: Aug 2010

Location: SW Missouri

Posts: 2,958

Time spent in forums: 1 Week 6 Days 3 h 7 m 10 sec
Reputation Power: 345

Try debugging the code by adding some println statements that will print out the values of variables as the code executes and show you why it goes into an infinite loop.
It should show how the value of temp changes as the code executes.

March 6th, 2013, 06:48 AM

tvc3mye

Daniel Schildsky

Dev Shed Intermediate (1500 - 1999 posts)

Join Date: Mar 2004

Location: KL, Malaysia.

Posts: 1,534

Time spent in forums: 2 Weeks 4 Days 2 h 27 m 57 sec
Reputation Power: 1620

Send a message via Google Talk to tvc3mye

infinite loop

Just by looking at the codes, there are 2 exit criteria to escape the while loop:
a) temp is null.
b) temp.right is null.

You have to find out why either of these 2 conditions are not reached.

__________________
When the programming world turns decent, the real world will turn upside down.

Homework - Threaded Tree Traversal

Developer Shed Advertisers and Affiliates