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

1. Introduction

In this article, I will discuss how to create a Binary Tree/Binary Search Tree Preorder 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 Preorder Traversal.

Example 1

Preorder Traversal = [1,2,4,5,3,6,7]

Example 2

Preorder Traversal = [1,2,4,10,3,5,7,6,8]

Example 3

Preorder Traversal = [10,5,2,7,15,12,17]

3. Iterator for Binary Tree

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

Class signature:

class BSTPreorderIterator {

    public BSTPreorderIterator(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 BSTPreorderIterator {

    private final Deque<TreeNode> stack;

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

3. In Preorder traversal, we first visit the root. Then traverse the left subtree and then traverse the right subtree. In order to do that, we need to insert the root immediately in the stack inside of constructor.

public class BSTPreorderIterator {

    private final Deque<TreeNode> stack;

    public BSTPreorderIterator(TreeNode root) {
        stack = new ArrayDeque<>();
        if (root != null)
            stack.push(root);
    }

}

4. Implementing hasNext() method.

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

5. Implementing next() method. We need to pop() the node from the stack and return the value of that node. Before we return the value, we need to traverse the left node and then the right node. As we are using the stack, we should insert the right node first and then the left node. So when we pop the element out of the stack, we can pop the left element first.

public int next() {
    TreeNode node = stack.pop();    
    if (node.right != null) stack.push(node.right);
    if (node.left != null) stack.push(node.left);
    return node.val;
}

Entire implementation:

public class BSTPreorderIterator {

    private final Deque<TreeNode> stack;

    public BSTPreorderIterator(TreeNode root) {
        stack = new ArrayDeque<>();
        if (root != null)
            stack.push(root);
    }

    public int next() {
        TreeNode node = stack.pop();
        if (node.right != null)
            stack.push(node.right);
        if (node.left != null)
            stack.push(node.left);
        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(1) as we are just inserting the left and right nodes in the stack and removing one element out. All these operations take O(1) 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 Preorder Traversal of the Binary Tree using Recursion and Iteration.

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