BinarySearchTreeIterator [source code]

public class BinarySearchTreeIterator {
static
/****************************************************************************/
public class BSTIterator {
    Deque<TreeNode> stack;

    public BSTIterator(TreeNode root) {
        stack = new ArrayDeque <> ();
        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 res = stack.poll ();
        if (res.right != null) {
            TreeNode cur = res.right;
            while (cur != null) {
                stack.push (cur);
                cur = cur.left;
            }
        }
        return res.val;
    }
}
/****************************************************************************/
/**
 * Your BSTIterator will be called like this:
 * BSTIterator i = new BSTIterator(root);
 * while (i.hasNext()) v[f()] = i.next();
 */

    public static void main(String[] args) {
        int[][] inputs = {
            {1,2,3,4,5,6,7}, 
            {1,2,3,4,5},         
            {1,2,3,4,10000_00007,10000_00007,5}, 
            {1,2,3,4,5,10000_00007,7,6,10000_00007,10000_00007,9,10000_00007,8}, 
        };
        for (int i = 0; i < inputs.length; i++) {
            System.out.println (Printer.separator ());
            TreeNode root = TreeNode.bfsBuild (inputs[i]);
            String ser = TreeNode.serialize (root);
            StringBuilder sb = new StringBuilder ();
            BSTIterator bsti = new BSTIterator (root);
            String ans = (new IterativeDFS ()).guidedInOrder (root);
            while (bsti.hasNext ())
                sb.append (bsti.next () + " ");
            String output = sb.toString ();
            System.out.printf ("%s\n%s\n%s\n", 
                ser, Printer.wrap (output, output.equals (ans) ? 92 : 91), ans
            );
        }
    }
}

tag给的是Stack, 感觉有点凉;

trivial的做法就是直接存一个serialization, 放在一个数组里面, 这样设计起来就很简单;
当然出题人当然知道这个可能性了, 所以空间给了你限制;
面试的时候第一步或许可以提一下这个笨办法;

要求的空间限制是O(h), 或许是一个提示? 加上知道是Stack问题, 什么思路?

感觉跟iterative inorder的写法有点类似? 不是很确定, 可以写写看;

现在直觉是推大梁的传统的DFS写法, 应该肯定是可以写这个题目的, 或者说是专门为这个题目而生的, 因为那种写法就是很明确的要维护一个Stack;

我有点怀疑, 之前学的那个用guide的DFS写法, 不知道能不能解决这题;

感觉不是太好, 因为没有明确的比如从最小的开始的那种感觉;

先直接用传统做法写写看了;

轻松AC, 速度是5(98), 果然, 传统DFS还是很好写的; 我一开始自己写的时候, 还以为我忘记了iterative DFS的写法, 不过写下来, 脑子里用我的typical tree:

帮助思考, 感觉也不是特别复杂;

我突然想到一个问题, 我的这个next是不是O(1)时间? 要看你怎么分析了, 实际上是一个average的是可以认为是O(1)的; 但是worst case不是; 比如

这种的第一个get, 就是O(N)的;

为什么认为average是O(1), 因为每一个node最多被push一次和pop一次, 很常见的aggregate分析手段了;

重新看了一下题目, 时间O(1)还真的是average, 那么无所谓了;

UNFINISHED

editorial

https://leetcode.com/problems/binary-search-tree-iterator/discuss/52525/My-solutions-in-3-languages-with-Stack

I use Stack to store directed left children from root.
When next() be called, I just pop one element and process its right child as new root.
The code is pretty straightforward.

So this can satisfy O(h) memory, hasNext() in O(1) time,
But next() is O(h) time.

I can't find a solution that can satisfy both next() in O(1) time, space in O(h).

Java:

public class BSTIterator {  
    private Stack<TreeNode> stack = new Stack<TreeNode>();  

    public BSTIterator(TreeNode root) {  
        pushAll(root);  
    }  

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

    public int next() {  
        TreeNode tmpNode = stack.pop();  
        pushAll(tmpNode.right);  
        return tmpNode.val;  
    }  

    private void pushAll(TreeNode node) {  
        for (; node != null; stack.push(node), node = node.left);  
    }

代码都差不多的, 这个方法也有大家在讨论复杂度:

caikehe 3654 July 12, 2015 4:21 PMReport
The average time complexity of next() function is O(1) indeed in your case. As the next function can be called n times at most, and the number of right nodes in self.pushAll(tmpNode.right) function is maximal n in a tree which has n nodes, so the amortized time complexity is O(1).

写错了吧, pushAll里面left child应该是最多是O(N).
我认为这个分析不如我针对Stack的aggregate分析更好; 不过本质上应该是差不多的;

clark3 74 January 11, 2015 2:50 AMReport
Nice solution. It is actually breaks in-order traversal into hasNext() and next()

没错;

siyang3 495 February 28, 2015 2:45 PMReport
Your solution is indeed average O(1) time and O(h) space.
Each node will be visited at most twice-> average O(1) run time.
The stack will store at most h nodes -> O(h) space.

说到iterative DFS, 然后就有人上Morris了:

zmlzeze 11 July 8, 2017 2:06 PMReport
I think Morris Traversal meets the requirement of average O(1) time and O(h) space (or even better, O(1) space). Since traversing any tree will at least visit n nodes, if the total time complexity for getting n nodes is O(n), then the average time complexity for iterating each node can be considered as O(1).
The Morris Traversal time complexity for traversing all n nodes is O(n), and the averaged time complexity for getting each node is O(1); the space complexity is O(1) for storing only the current node. Using the Morris Traversal method to perform an inorder traversal on BST will generate the sorted array.
In this case, next() function requires the next smallest element to be returned, so we break the traversing loop every time a node is traversed. Although there is a loop to find the inorder predecessor, which is O(log n) in the worst case, not every node needs this loop and the averaged time complexity is guaranteed to be O(1).
However, the obvious drawback is the Morris Traversal will temporarily change the tree structure. If the tree is used elsewhere before being entirely traversed, this method will cause problems.

public class BSTIterator {  

    private TreeNode root,cur;  
    public BSTIterator(TreeNode root) {  
        root = root;  
        cur = root;  
    }  

    public boolean hasNext() {  
        return cur != null;  
    }  

    public int next() {  
        int r = 0;  
        while(cur!=null){  
            if(cur.left==null){  
                r = cur.val;  
                cur = cur.right;  
                // Got the node, break loop  
                break;  
            }else{  
                TreeNode node = cur.left;  
                while(node.right!=null&&node.right!=cur){  
                    node  = node.right;  
                }  
                if(node.right==null){  
                    node.right = cur;  
                    cur = cur.left;  
                }else{  
                    node.right = null;  
                    r = cur.val;  
                    cur = cur.right;  
                    // Got the node, break loop  
                    break;  
                }  
            }  
        }  
        return r;  
    }  
}

你艺高人胆大好吧, 我反正真正面试的时候是真的不敢主动选择去写Morris的; 到现在都不记得具体是怎么一回事;

Morris的有点他也说了, 主要就是空间几乎是最优了;

作为iterator的场景来说, Morris其实不是特别的合适, 因为iterator很多时候还真的不是短时间内就能够用完拉倒; 很多时候一个iterator的完整遍历需要花不少时间; 这个concurrency问题就格外的明显;
不过了解一个做法也是有意思的;

大概跑一个trace还是能看懂的; 不过这个东西真正面试要是写出来也是几乎是默写的程度;

当时说推大梁写法其实也是有两种套路的, 这里有人写出了第二种套路(while的header里面有一个||的那种):

真的要写也不是不行吧; Morris最难写的其实是PostOrder; 如果是InOrder, 如果记忆的熟练, 其实是可以写的;

突然想到一个问题, 这题给的题目要求虽然是BST的, 但是实际上最后做的就是一个general的binary tree的, 是吧? 根本没有用到BST Property;

FF_Ti 110 September 20, 2017 12:48 PMReport
The implementation of BST iterator is very similar to binary search tree Inorder traversal. Inorder using stack and two while loop. However, in the iterator, the first while condition become hasNext() and the code inside the first while condition become next().
For your reference, It is the code of binary search tree Inorder traversal.

class Solution {  
    public List<Integer> inorderTraversal(TreeNode root) {  
        Stack<TreeNode> stack = new Stack();  
        List<Integer> res = new ArrayList();  
        while (root != null || !stack.isEmpty()) {  
            while (root != null) {  
                stack.push(root);  
                root = root.left;  
            }  
            root = stack.pop();  
            res.add(root.val);  
            root = root.right;  
        }  
        return res;  
    }  
}

And below is the BST iterator.

public class BSTIterator {  

    Stack<TreeNode> stack;  
    TreeNode node;  
    public BSTIterator(TreeNode root) {  
        stack = new Stack();  
        node = root;  
    }  

    public boolean hasNext() {  
        return !stack.isEmpty() || node != null;  
    }  

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

没什么毛病; 不过我还是用我自己之前的那个写法我认为更好掌握; 真正面试的时候如果你只是单纯记住了一个算法, 估计是不敢往白板上写的;

了解一下没毛病;

基本就这些了;

Problem Description

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.

Credits:
Special thanks to @ts for adding this problem and creating all test cases.

Difficulty:Medium
Total Accepted:132.1K
Total Submissions:301.6K
Contributor:ts
Companies
googlefacebookmicrosoftlinkedin
Related Topics
stacktreedesign
Similar Questions
Binary Tree Inorder TraversalFlatten 2D VectorZigzag IteratorPeeking IteratorInorder Successor in BST