post order traversal in binary tree using one stack

Question

I want to make a post order traversal of a binary tree using one stack only. This is my code , first of all i am pushing left elements into the stack till I reach null. Then I pop an element and check whether the popped out element and the right element of the current stack top is same or not. But somehow this is going into infinite loop. can you tell me why??

public void postorderonestack(BinNode root)
{
    BinStack s=new BinStack();

    while(true)
    {
        if(root!=null)
        {
           s.push(root);
           root=root.getLeft();
        }
        else
        {
            if(s.isEmpty())
            {
                System.out.println("Stack is Empty");
                return;
            }

            else if( s.top().getRight()==null)
            {
                root=s.pop();
                System.out.println(root.getKey());

                if(root==s.top().getRight())
                {
                   System.out.print(s.top().getKey());
                   s.pop();
                }
            }

            if(!s.isEmpty())
              root=s.top().getRight();

           else root=null;
        }
    }
}

Can you provide an example that it gets stuck on?

Scott Hunter
– Scott Hunter

2013-12-24 12:50:50 +00:00
Commented Dec 24, 2013 at 12:50 — Scott Hunter
– Scott Hunter, Commented Dec 24, 2013 at 12:50

Community · Accepted Answer · 2017-05-23 10:34:08Z

2

This is the code from my answer to another question (Post order traversal of binary tree without recursion). It works with one stack and doesn't use visited flag.

private void postorder(Node head) {
  if (head == null) {
    return;
  }
  LinkedList<Node> stack = new LinkedList<Node>();
  stack.push(head);

  while (!stack.isEmpty()) {
    Node next = stack.peek();

    if (next.right == head || next.left == head ||
        (next.left == null && next.right == null)) {
      stack.pop();
      System.out.println(next.value);
      head = next;
    }
    else {
      if (next.right != null) {
        stack.push(next.right);
      }
      if (next.left != null) {
        stack.push(next.left);
      }
    }
  }
}

edited May 23, 2017 at 10:34

CommunityBot

11 silver badge

answered Dec 25, 2013 at 4:27

tcb

2,83222 silver badges20 bronze badges

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

Comments

sebii · Accepted Answer · 2013-12-24 19:57:08Z

2

Why not do it recursively?

public void postorder(BinNode root) {
    if (root == null)
        return;
    postorder(root.getLeft());
    postorder(root.getRight());
    System.out.println(root.getKey());
}

answered Dec 24, 2013 at 19:57

sebii

5162 silver badges6 bronze badges

1 Comment

VIN Over a year ago

Sure this is a way, but finding other options.

Dheerendra Kulkarni · Accepted Answer · 2013-12-24 13:12:26Z

0

There is an infinite loop in this code lets consider an Right skewed tree to illustarte this:

1 has a right child 2

2 has a right child 3

3 is a leaf node

In first 3 loops 1 follwed by 2 followed by 3 will be pushed on to the stack. Now on fourth loop it enters else part now it prints 3 followed by 2 and pops both.

after the statement

else if( s.top().getRight()==null)

the statement

if(!s.isEmpty())

will push 2 again on stack. This causes infinite loop.

The code is flawed.

The statement

if(root==s.top().getRight())

should become a while loop to fix this issue.

answered Dec 24, 2013 at 13:12

Dheerendra Kulkarni

2,7541 gold badge19 silver badges18 bronze badges

Comments

Juan Zhao · Accepted Answer · 2024-11-16 11:53:50Z

0

Here is my code

const ans = []
const stack = []
var cur = root
while (cur) {
    ans.push(cur.val)
    stack.push(cur)
    cur = cur.right
}
while (stack.length) {
    cur = cur.pop()
    if (cur.left) {
        cur = cur.left
        while (cur) {
            ans.push(cur.val)
            cur = cur.right
        }
    }
}

return ans.reverse()

answered Nov 16, 2024 at 11:53

Juan Zhao

112 bronze badges

Collectives™ on Stack Overflow

post order traversal in binary tree using one stack

4 Answers 4

Comments

1 Comment

Comments

Comments

Your Answer

Hot Network Questions

Collectives™ on Stack Overflow

4 Answers 4

Comments

1 Comment

Comments

Comments

Your Answer

Sign up or log in

Post as a guest

Related