Binary Search Tree Iterator

Problem: Implement an iterator over a binary search tree (BST). Your iterator should perform following operations -

1. Next - Return the next smallest number in the BST.
2. HasNext - Check if there is any element.

Approach: We can see that we need a inorder traversal here. What we can do is we can store all the nodes in an array using inorder traversal but that will increase the space a lot. If we want to reduce space then we can actually have a member say k and can return kth smallest node by doing inorder traversal every time when somebody calls Next.

Now if we go with recursion approach of inorder traversal, we always have to start from root but if we use the stack approach, we can do little better both in terms of time and space.

    public class BSTIterator

    {

        public BSTIterator(BinaryTreeNode root)

        {

            this.stack = new Stack<BinaryTreeNode>();

            this.PushTillLeftMost(root);

        }

        public int Next()

        {

            BinaryTreeNode node = stack.Pop();

            if (node.RightNode!= null)

            {

                this.PushTillLeftMost(node.RightNode);

            }

            return node.Value;

        }

        public bool HasNext()

        {

            return stack.Count > 0;

        }

        private void PushTillLeftMost(BinaryTreeNode node)

        {

            while (node != null)

            {

                stack.Push(node);

                node = node.LeftNode;

            }

        }

        private Stack<BinaryTreeNode> stack;

    }