Binary Search Tree Iterator

Binary Search Tree Iterator

32%

Accepted

Design an iterator over a binary search tree with the following rules:

• Elements are visited in ascending order (i.e. an in-order traversal)
• next() and hasNext() queries run in O(1) time in average.

Have you met this question in a real interview? 

Yes

Example

For the following binary search tree, in-order traversal by using iterator is[1, 6, 10, 11, 12]

   10
 /    \
1      11
 \       \
  6       12

Challenge

Extra memory usage O(h), h is the height of the tree.

Super Star: Extra memory usage O(1)

public class Solution {

    //@param root: The root of binary tree.

    Stack<TreeNode> stack;

    public Solution(TreeNode root) {

        // write your code here

        stack = new Stack<TreeNode>();

        pushLeft(root);

    }

    //@return: True if there has next node, or false

    public boolean hasNext() {

        // write your code here

        return !stack.isEmpty();

    }

    

    //@return: return next node

    public TreeNode next() {

        // write your code here

        TreeNode next = stack.pop();

        pushLeft(next.right);

        return next;

    }

    private void pushLeft(TreeNode root){

        while(root != null){

            stack.push(root);

            root = root.left;

        }

    }

}