## Introduction

This is going to be a short post. The problem statement at hand is to write PostOrder Node Iterator of Binary Tree. For those who do not know the Iterator Design Pattern or Post Order Successor, check the next section.## Iterator Design Pattern

This pattern is used to iterate through a collection or group. The Java Iterator supports the following three methods :`hasNext()`

: returns a boolean true if the collection has elements after the last returned element, false otherwise.`next()`

: returns the next element in the collection.`remove()`

: removes the element from the collection, which was returned last.

## Post Order Successor of a binary tree node

The`next()`

method above returns the next element in the collection. The question is about choosing the next element. Which node of the tree, is the next element to be returned.
For this problem we consider the next element to be the post order successor, which ideally is the node of the tree which is visited next to the current node in a post order traversal.
A more formal definition of the post order successor of a node is as follows:
- If the node is a left child of its parent
- If the parent has a right subtree T'. It is the left most leaf of T'
- If the parent doesn't have a right subtree. It is the parent itself

- If the node is a right child of its parent, its the parent itself.

##### The idea behind this solution

As it is a simple binary tree, it doesn't have a parent pointer. Now, we will need a stack data structure, so that we will have a reference to the parent and grand parents up to the root in the stack. The`iterator`

needs to keep a track of the last returned node. Hence, we will have an instance level property.
Also, the state of the stack must be retained for various invocation of the `next()`

method.
Implementation of the `remove()`

method is left for reader to implement on their own for practice. Let us check, what can we do to implement the `hasNext()`

method.
##### hasNext() method

In a post order sequence, the root is the last node to be visited. Hence the iterator will always have a next element, if the last returned element is not null.##### next() method

We have to find the post order successor of the previously returned node. A lot of cases arise:- The previously returned node was null, which means the next method is invoked for the first time. So push the root on to the Stack.
- Check if a left child exists for the node at the top of the Stack. Add the left child to the Stack and repeat this step.
- If no left child exists, check if a right child exists for the node at the top of the Stack. If yes, push the right child to the Stack and repeat the step 1.

- A previously returned node exists.
- Check if the node is the left child of its parent (the parent is the top element on the stack). If yes, then check if there is a right child for the parent. If yes, follow the above sequence of steps. If no right child exists, pop the parent from the Stack and mark it as previous node and return.
- If the node is the right child of its parent, pop the parent from the Stack and mark it as previous node and return.

## Source Code - PostOrder Node Iterator of Binary Tree

You can download the complete source with many running test cases from Github Link of TechieMe.public BNode next() { BNode tempNode = null; if (previousNode == null && root != null) { tempNode = root; S.push(tempNode); } tempNode = S.peek(); boolean breakLoop = false; do { // if right child is previously returned node , no need to do anything, we just need to return its parent as per our definition if (tempNode.right == previousNode && previousNode != null) { breakLoop = true; } else { if (tempNode.left == previousNode && tempNode.right == null) { breakLoop = true; } else { while (tempNode.left != null && previousNode != tempNode.left) { tempNode = tempNode.left; S.push(tempNode); } if (tempNode.right != null) { tempNode = tempNode.right; S.push(tempNode); } } // if this is a leaf node, we need to break out and return this node. if (tempNode.left == null && tempNode.right == null) breakLoop = true; } } while (!breakLoop); previousNode = S.pop(); return previousNode; }

## Conclusion

This approach can be extended for writing all the combinations like Post Order Predecessor, Inorder predecessor and successor and Preorder predecessor and successor. You can always comment if you find other ones tough. Also, we didn't use recursion stack, because the recursion stack is local to a method invocation and we needed a stack to persist across various invocation of the`next()`

method.
Don’t forget to **subscribe to TechieMe**to get updates on latest posts.