PostOrder Node Iterator of Binary Tree

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.

PostOrder Node Iterator of Binary Tree

In the adjacent diagram, every solid color node’s post order successor is the node with the same color solid border.

This means the node with value 8 is the successor of 10. 11 is successor of 4 and 7 is successor of 6

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.
      1. 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.
      2. 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.
      1. 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.
      2. If the node is the right child of its parent, pop the parent from the Stack and mark it as previous node and return.

This will make more sense with a source code and diagram, so here is a supporting diagram. The below animation shows each the invocation of next method and in each invocation the value of the previous node changes.
PostOrder Node Iterator of Binary Tree

There are invocation where we push a lot of nodes in the stack and there are invocations where we just pop from the Stack and return.

You can very well see that if the previous node was the right child of its parent, we just pop one node and return it. If the previous node’s parent doesn’t have a right child we just pop a node and return. This aligns with our formal definition of the post order successor.

Also, if the previous node was the left child of its parent we return the left most leaf of the right child, for e.g. if previous node is 4 then we return 11 for the next invocation.

Source Code – PostOrder Node Iterator of Binary Tree

You can download the complete source with many running test cases from Github Link of TechieMe.

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.