Iterative Post order traversal without visited array

Question

I have recently started learning computer science and Java coding and came across Traversal techniques. I am writing a Java code using Stack. I have been with this issue and couldn't find any solution. Is there anyway we can implement Post Order traversal using only one stack (without any extra data structure or extra space) ?

I have tried doing it and here is my code.

class node {
int data;
node left, right;
node(int val){
    data = val;
    left = right = null;
}
}
 public class binaryt {

public static void postorder(node root) {
    node current = root;
    Stack<node> st = new Stack<>();
    System.out.println();
    System.out.print("Post-order : ");  
    while(current!=null) {
        st.push(current);
        current = current.left;
    }
    while(!st.empty()) {
        current = st.pop();
        if(current.right==null) {
            System.out.print(current.data+" ");
            current = null;
        }
        else {
            st.push(current);
            current = current.right;
            while(current!=null) {
                st.push(current);
                current = current.left;
            }
        }
    }
}
public static void main(String[] args) {
    node root=null;


    root = new node(12);
    root.left = new node(8);
    root.left.left = new node(2);
    root.left.right = new node(9);
    root.right= new node(16);
    root.right.left= new node(13);
    root.right.right= new node(18);

    postorder(root);
}

}

I am unable to find what's wrong with the code as it is going in infinite loop. If anyone could help me, that would be huge favor. Thank you so much.

class node { int data; node left, right; node(int val){ data = val; left = right = null; } } — Piyali Thorat
– Piyali Thorat, Commented Aug 30, 2018 at 11:18
edit your question instead of commenting, also show how you are calling postorder method — Derrick
– Derrick, Commented Aug 30, 2018 at 11:22

John Humphreys · Accepted Answer · 2018-08-30 11:57:53Z

1

The best way to learn these annoying algorithms is to suffer a bit and find your own solution that will stick in your brain - so you're doing the right thing. This one is always hard for me.

do
- while(root != null)
  - push root.right to stack if not null
  - push root
  - root = root.left to stack
- root = stack.pop()
- if (root.right == stack.peek)
  - stack.pop()
  - push root to stack
  - root = root.right
- else
  - print root
  - root = null;
while stack ! empty

Your Problem

So, there are probably a few general things wrong in the attempt you showed. But here's the one I'd fix first, then I think you'll be able to get the others:

You can't just go left down the whole tree to start with. You need to go left only after you check the right node and add it to the stack. Remember, a recursive implementation would already have the root/current frame existing, then it would call the left and right trees. So, that means the current frame goes last after the left and right calls finish. So, the function call stack logically holds the left sub-tree, then the right-sub-tree, then the current frame.

answered Aug 30, 2018 at 11:57

John Humphreys

39.8k44 gold badges167 silver badges262 bronze badges

Sign up to request clarification or add additional context in comments.

5 Comments

vividpk21 Over a year ago

You can go directly down the left subtree, check my solution, java stacks allow you to access elements by index and delete by index as well so it's not really an issue unless you are going for something that will be holding millions of entries. I do agree he should learn himself though to better understand the concepts and how they apply to computer science.

John Humphreys Over a year ago

No, he's trying to implement an iterative post-order traversal. It is way harder than the recursive solution. Try it yourself :). Iterative literally means that you don't use recursion; that makes it way more efficient because you're not doing a function call on every level. The hard part is mimicking the recursive logic.

vividpk21 Over a year ago

Lmao I missed the title completely, oops. I'll give it a look and edit my post.

John Humphreys Over a year ago

I assume he’s mostly looking for editing his code to understand his problem specifically. It’s very easy to google a working solution for this one, it’s a popular interview question... unfortunately.

Piyali Thorat Over a year ago

@JohnHumphreys-w00te Thank you John for the insights and algorithm. Wow your algorithm looks clean and good. Thanks!

Raj · Accepted Answer · 2018-08-30 12:06:19Z

1

This is what is happening in your code :

first you are pushing 12,8 and 2 in the Stack
Then there is no left child for 2 , so you come to while
now 2 is popped out , and it has no right child, so now two values in stack 8,12
Next comes 8 it has a right child, you are pushing 8 into Stack again.
Now you are taking 9 as current and pushing it into Stack.
Now you are checking left of 9 which is null.
so you are again starting with while(!st.empty()) { loop which has elements 9, 8,12
again same thing repeats and your while loop never ends

you can also see on console : Post-order : 2 9 9 9 9 ..... Continues

So that is the issue.

Below is a solution :

public static void postorderIter( node root) {
    if( root == null ) return;

    Stack<node> s = new Stack<node>( );
    node current = root;

    while( true ) {

        if( current != null ) {
            if( current.right != null ) 
                s.push( current.right );
            s.push( current );
            current = current.left;
            continue;
        }

        if( s.isEmpty( ) ) 
            return;
        current = s.pop( );

        if( current.right != null && ! s.isEmpty( ) && current.right == s.peek( ) ) {
            s.pop( );
            s.push( current );
            current = current.right;
        } else {
            System.out.print( current.data + " " );
            current = null;
        }
    }
}

answered Aug 30, 2018 at 12:06

Raj

7278 silver badges25 bronze badges

2 Comments

Piyali Thorat Over a year ago

Thank you Raj for helping me understand the issue.:)

Raj Over a year ago

@Piyali Thorat Welcome .. Accept any one of the three answers :)

vividpk21 · Accepted Answer · 2018-08-30 11:53:39Z

0

Here's an example that relies on recursion to make it more readable.

public static void postorder(node root) {
    Stack<node> nodes = new Stack<>();
    node curr = root;

    postOrderRecursive(curr, nodes);

    int size = nodes.size();
    while(size > 0){

        System.out.println(nodes.elementAt(0).data);
        nodes.remove(0);
        size = nodes.size();
    }
}
private static void postOrderRecursive(node n, Stack<node> nodes){
    if(n.left != null)
        postOrderRecursive(n.left, nodes);
    if(n.right != null)
        postOrderRecursive(n.right, nodes);

    nodes.push(n);
}

Output given your initialization: 2 9 8 13 18 16 12

answered Aug 30, 2018 at 11:53

vividpk21

3841 silver badge12 bronze badges

1 Comment

Piyali Thorat Over a year ago

Thanks Vivid! However, I was looking for an iterative implementation.:)

Collectives™ on Stack Overflow

Iterative Post order traversal without visited array

3 Answers 3

5 Comments

2 Comments

1 Comment

Your Answer

Hot Network Questions

Collectives™ on Stack Overflow

3 Answers 3

5 Comments

2 Comments

1 Comment

Your Answer

Sign up or log in

Post as a guest

Related