Binary Search Tree Iterator

Implement an iterator over a binary search tree (BST). Your iterator will be initialized with the root node of a BST.

Calling next() will return the next smallest number in the BST.

Note: next() and hasNext() should run in average O(1) time and uses O(h) memory, where h is the height of the tree.

public class BSTIterator {
    Stack<TreeNode> stack;  

    public BSTIterator(TreeNode root) {
        stack = new Stack<TreeNode> ();
        //store each left node in the stack
        //the smallest left node is put on the top of the stack
        while (root != null) {
            stack.push(root);
            root = root.left;
        }
    }  

    /** @return whether we have a next smallest number */
    public boolean hasNext() {
        return !stack.isEmpty();
    }  

    /** @return the next smallest number */
    public int next() {
        TreeNode node = stack.pop();
        int ret = node.val;
        //check if the current node has right child
        if (node.right != null) {
            //update the node
            node = node.right;
            //push all of its left child in the stack
            while (node != null) {
                stack.push(node);
                node = node.left;
            }
        }
        return ret;
    }
}
Advertisements

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s