Given the root of a Binary Tree, implement a Postorder Iterator with methods hasNext() and next().

1. Introduction

In this article, I will discuss how to create a Binary Tree/Binary Search Tree Postorder iterator.

This article is part of Binary Tree-Traversals. Read more about Binary Tree traversals here.

2. Content

Below is an example of the Binary Tree and its Postorder Traversal.

Example 1: Postorder Traversal = [4,5,2,6,7,3,1]

Example 2: Postorder Traversal = [10,4,2,7,5,8,6,3,1]

3. Iterator for Binary Tree

1. We will name our class as BSTPostorderIterator. The root node will be input to a parameterized constructor.

Class signature:

class BSTPostorderIterator {

    public BSTPostorderIterator(TreeNode root) {
    }
}

2. We will need an auxiliary data structure to store the elements that we will traverse in the tree. Let us use the ArrayDeque class.

class BSTPostorderIterator {

    private final Deque<TreeNode> stack;

    public BSTPostorderIterator(TreeNode root) {
        stack = new ArrayDeque<>();
    }
}

3. In Postorder traversal, we first visit the left subtree, then right subtree, and last, the root node. In order to do that, we need to insert the left nodes into the stack. And if the left node is null, we should insert the right nodes.

public class BSTPostorderIterator {

    private final Deque<TreeNode> stack;

    public BSTPostorderIterator(TreeNode root) {
        stack = new ArrayDeque<>();
        init(root);
    }

    private void init(TreeNode root) {
        while (root != null) {
            stack.push(root);
            if (root.left != null)
                root = root.left;
            else
                root = root.right;
        }
    }

}

4. Implementing hasNext() method.

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

5. Implementing next() method. We need to pop() the node from the stack. If the stack is empty, then return the element. Else this node is stack’s peek value’s left child, then insert the right subtree in stack.

public int next() {
    TreeNode node = stack.pop();
    if (!stack.isEmpty()) {
        if (node == stack.peek().left) {
            // find next leaf in right sub-tree
            init(stack.peek().right);
        }
    }
    return node.val;
}

Entire implementation:

public class BSTPostorderIterator {

    private Deque<TreeNode> stack;

    public BSTPostorderIterator(TreeNode root) {
        stack = new ArrayDeque<>();
        init(root);
    }

    private void init(TreeNode root) {
        while (root != null) {
            stack.push(root);
            if (root.left != null)
                root = root.left;
            else
                root = root.right;
        }
    }

    public int next() {
        TreeNode node = stack.pop();
        if (!stack.isEmpty()) {
            if (node == stack.peek().left) {
                // find next leaf in right sub-tree
                init(stack.peek().right);
            }
        }
        return node.val;
    }

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

Time Complexity:

1. hasNext() method: O(1) as we are just checking if the stack is empty or not.
2. next() method: O(n) as we are just inserting the left and right subtree in the stack and removing one element out. All these operations take O(n) time.

Space Complexity:

1. O(n) where n is the total number of nodes in the Binary Tree.

4. Conclusion

In this article, we saw Postorder Traversal of the Binary Tree using the Iterator.

GitHub Link: https://github.com/savanibharat/justamonad-tutorials/blob/master/justamonad-tutorials-leetcode/src/main/java/com/justamonad/tutorials/leetcode/tree/BSTPostorderIterator.java