Problem

Implement an iterator that performs a Postorder Traversal on a binary tree. In postorder traversal, the nodes of a binary tree are visited in the following order:

  • Left subtree
  • Right subtree
  • Root node

Iterator Design Pattern

The iterator pattern facilitates traversal over a collection or dataset. Java’s Iterator provides three key methods:

  • hasNext(): Returns true if there are remaining elements to iterate, otherwise false.
  • next(): Retrieves the next element in the collection.
  • remove(): Deletes the most recently returned element from the collection.

Examples

Example 1

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15

Input:
 Binary Tree: 
         1
        / \
       2   3
      / \
     4   5
 
Output:
Iterator Outputs: 4, 5, 2, 3, 1

Explanation:
Postorder traversal visits nodes in the order:
Left subtree -> Right subtree -> Root. 
Here, 4 and 5 are left and right children of 2, then visit 2, then 3, and lastly the root 1.

Example 2

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13

Input:
 Binary Tree:
         1
        /
       2
      /
     3
 
Output:
Iterator Outputs: 3, 2, 1

Explanation:
The binary tree is left-skewed. Postorder traversal visits the deepest leftmost child (3), then its parent (2), and finally the root (1).

Solution

Method 1 - Using Stack

Postorder traversal is a depth-first traversal that focuses on visiting a node only after visiting its children. To implement an iterator for postorder traversal:

  1. We need to ensure that we traverse the left and right subtree before visiting the root node.
  2. Unlike recursive traversal, the iterator is implemented using a stack (since recursion internally uses a stack).
  3. The idea is to keep track of already visited nodes and process the current node only once its children are processed.

The next() method retrieves the subsequent element in the collection, raising the question of how the next element is determined. Specifically, for this problem, the next element corresponds to the postorder successor, which is the tree node visited immediately after the current node in postorder traversal.

A formal definition of the postorder successor is as follows:

  • If the node is the left child of its parent:
    • When the parent has a right subtree ( T’ ), the successor is the leftmost leaf of ( T’ ).
    • If the parent lacks a right subtree, the successor is the parent itself.
  • If the node is the right child of its parent, then the successor is the parent.
graph TD;
A(1)
B(2)
C(3)
D(4):::orangeFill
E(5)
F(6):::greenFill
G(7):::greenBorder
H(8):::blueBorder
I(9)
J(10):::blueFill
K(11):::orangeBorder
L(12)

A --- B & C
B --- D & E
C --- F & G
D --- H
D ~~~ N1:::hidden
H --- I & J
E ~~~ N2:::hidden
E --- K
F ~~~ N3:::hidden
F --- L

classDef hidden display:none
classDef blueFill fill:#1E90FF,stroke:#000,stroke-width:1px,color:#fff;
classDef blueBorder fill:none,stroke:#1E90FF,stroke-width:2px,color:#000;
classDef greenFill fill:#32CD32,stroke:#000,stroke-width:1px,color:#fff;
classDef greenBorder fill:none,stroke:#32CD32,stroke-width:2px,color:#000;
classDef orangeFill fill:#FFA500,stroke:#000,stroke-width:1px,color:#fff;
classDef orangeBorder fill:none,stroke:#FFA500,stroke-width:2px,color:#000;

In the accompanying diagram, each solid-coloured node’s postorder successor is marked with the same solid border colour. For instance, node 8 is the successor of 10, 11 follows 4, and 7 is the successor of 6.

Intuition

In a basic binary tree without parent pointers, we require a stack to maintain references to the parent as well as ancestors up to the root. This enables traversal while keeping hierarchy intact. Additionally, the iterator needs to track the last node that was returned, making it important to have an instance-level variable for this. The state of the stack must persist across multiple calls to the next() method, ensuring traversal continuity. For practice, readers can implement the remove() method on their own. Meanwhile, let’s focus on implementing the hasNext() and next() methods.

Approach

hasNext() Method

In postorder traversal, the root node is the final node visited. Consequently, the iterator guarantees a next element as long as the last returned node is not null.

next() Method

To fetch the postorder successor of the previously returned node, several scenarios must be addressed:

  • If the previously returned node is null: This means the next() method is invoked for the first time. Start by pushing the root node onto the stack.
    1. Check if the top node has a left child. If it does, push the left child onto the stack and repeat.
    2. If no left child is found, check for a right child. If present, push it onto the stack and repeat step 1.
  • If there is a previously set node:
    1. Determine if the node is the left child of its parent (the parent is at the top of the stack). If true, check if the parent has a right child. If the right child exists, follow the previous sequence of steps. If no right child exists, pop the parent from the stack, mark it as visited, and return it.
    2. If the node is the right child of its parent, simply pop the parent from the stack, mark it as visited, and return it.

The logic is visualised through the accompanying code and animation. The diagram demonstrates how the next() method processes each invocation, updating the “previous node” appropriately.

Here is a video if you want to prefer pausing to see dry run:

  1. In some cases, multiple nodes are pushed onto the stack, while in others, nodes are simply popped off and returned directly.
  2. If the previous node was the right child, the method pops one node and returns it immediately. Similarly, if the parent of the previous node lacks a right child, it pops and returns the node.
  3. When the previous node was the left child, the method proceeds to find the leftmost leaf of the parent’s right child (e.g., when the previous node is 4, the next call returns 11).

This behaviour aligns perfectly with the formal definition of the postorder successor and ensures correctness during traversal.

Code

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54

// PostOrder Iterator class
public class PostOrderIterator {
	private Stack<TreeNode> stack;
	private TreeNode prevNode;

	public PostOrderIterator(TreeNode root) {
		stack = new Stack<>();
		prevNode = null;
		if (root != null) {
			stack.push(root);
		}
	}

	public boolean hasNext() {
		return !stack.isEmpty();
	}

	public int next() {
		while (hasNext()) {
			TreeNode curr = stack.peek();

			// Traverse left subtree
			if (curr.left != null && prevNode != curr.left && prevNode != curr.right) {
				stack.push(curr.left);
			}
			// Traverse right subtree
			else if (curr.right != null && prevNode != curr.right) {
				stack.push(curr.right);
			}
			// Process current node
			else {
				stack.pop();
				prevNode = curr;
				return curr.val;
			}
		}
		return -1; // This line should never be reached if `hasNext()` is used correctly.
	}

    public static void main(String[] args) {
        // Example usage
        TreeNode root = new TreeNode(1);
        root.left = new TreeNode(2);
        root.right = new TreeNode(3);
        root.left.left = new TreeNode(4);
        root.left.right = new TreeNode(5);

        PostOrderIterator iterator = new PostOrderIterator(root);

        while (iterator.hasNext()) {
            System.out.print(iterator.next() + " ");
        }
    }
}
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43

# PostOrder Iterator class
class PostOrderIterator:

	def __init__(self, root):
		self.stack = []
		self.prevNode = None
		if root:
			self.stack.append(root)

	def has_next(self):
		return bool(self.stack)

	def next(self):
		while self.has_next():
			curr = self.stack[-1]

			# Traverse left subtree
			if curr.left and self.prevNode != curr.left and self.prevNode != curr.right:
				self.stack.append(curr.left)
			# Traverse right subtree
			elif curr.right and self.prevNode != curr.right:
				self.stack.append(curr.right)
			# Process current node
			else:
				self.stack.pop()
				self.prevNode = curr
				return curr.val

    # Example usage
    def example():
        root = Solution.TreeNode(1)
        root.left = Solution.TreeNode(2)
        root.right = Solution.TreeNode(3)
        root.left.left = Solution.TreeNode(4)
        root.left.right = Solution.TreeNode(5)

        iterator = Solution.PostOrderIterator(root)

        while iterator.has_next():
            print(iterator.next(), end=" ")

# Example usage:
PostOrderIterator.example()

Complexity

  • ⏰ Time complexity: O(n). Each node is visited exactly once.
  • 🧺 Space complexity: O(h), where h is the height of the tree (due to stack space for recursion simulation).