Can anyone verify if this is O(1) time O(h) space solution?

  • 0
    public class BSTIterator {
        Stack<TreeNode> stack;
        public BSTIterator(TreeNode root) {
            stack = new Stack<TreeNode>();
        void  addLeftNodes(TreeNode node) {
            while (node != null) {
                node = node.left;
        /** @return whether we have a next smallest number */
        public boolean hasNext() {
            return !stack.isEmpty();
        /** @return the next smallest number */
        public int next() {
            TreeNode next = stack.pop();
            // Add its right node's left nodes onto stack
            return next.val;

  • 2

    Yes. Your next() runs in average O(1) time.
    The *next()*it is called n times, while in all the runtime of next(), each of the n nodes enters the stack at most 1 time (some nodes enter during construction) and leaves the stack exactly 1 time.

    And the space cost is O(h) time.
    The stack size grows only in addLeftNodes().
    Each time addLeftNodes() finishes, the node at top of the stack is a leaf.
    At the same time, right below each node is its parent or the parent of its parent.
    Thus, after addLeftNodes(), the node sequence in stack forms a (sometimes incompleted) path from root to a leaf. Such a path always has a length less than the height of the tree.

Log in to reply

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.