Leetcode: Binary Search Tree Iterator

Leetcode: 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.

这是一道很经典的题目，考的非递归的中序遍历。其实这道题等价于写一个二叉树中序遍历的迭代器。需要内置一个栈，一开始先存储到最左叶子节点的路径。在遍历的过程中，只要当前节点存在右孩子，则进入右孩子，存除从此处开始到当前子树里最左叶子节点的路径。

1. public class BSTIterator {  
2.     Stack<TreeNode> stack;  
3.   
4.     public BSTIterator(TreeNode root) {  
5.         stack = new Stack<TreeNode>();  
6.         while (root != null) {  
7.             stack.push(root);  
8.             root = root.left;  
9.         }  
10.     }  
11.   
12.     /** @return whether we have a next smallest number */  
13.     public boolean hasNext() {  
14.         return !stack.isEmpty();  
15.     }  
16.   
17.     /** @return the next smallest number */  
18.     public int next() {  
19.         TreeNode node = stack.pop();  
20.         int ret = node.val;  
21.         if (node.right != null) {  
22.             node = node.right;  
23.             while (node != null) {  
24.                 stack.push(node);  
25.                 node = node.left;  
26.             }  
27.         }  
28.         return ret;  
29.     }  
30. } 

https://leetcode.com/discuss/20001/my-solutions-in-3-languages-with-stack

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.

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

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

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

    /** @return the next smallest number */
    public int next() {
        TreeNode tmpNode = stack.pop(); // handle when stack is empty
        pushAll(tmpNode.right);
        return tmpNode.val;
    }

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

https://leetcode.com/discuss/67872/very-concise-solution-by-using-stack-in-java

https://leetcode.com/discuss/20147/java-a-solution-of-15-lines
https://discuss.leetcode.com/topic/6575/my-solutions-in-3-languages-with-stack

The complexity of the "hasNext()" is O(1). While the "next()" needs to refresh the stack, which in the best case (leaf) takes constant time, and in the worst case, it would take up to "h"steps. The overall cost of "next()" is then amortized over the number of nodes. I don't have the precise proof, but it seems to be O(1) on average.

//refreshStack reuse the code

Stack<TreeNode> stack = new Stack<TreeNode>(); private void refreshStack(TreeNode iter){ while(iter != null){ stack.push(iter); iter = iter.left; } } public BSTIterator(TreeNode root) { this.refreshStack(root); } /** @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(); if(node != null){ this.refreshStack(node.right); return node.val; } return -1; // should throw exception here. }

X.

http://www.jiuzhang.com/solutions/implement-iterator-of-binary-search-tree/

https://leetcode.com/discuss/22137/my-java-accepted-solution

public class Solution {
    private Stack<TreeNode> stack = new Stack<>();
    private TreeNode curt;
    
    // @param root: The root of binary tree.
    public Solution(TreeNode root) {
        curt = root;
    }

    //@return: True if there has next node, or false
    public boolean hasNext() {
        return (curt != null || !stack.isEmpty());
    }
    
    //@return: return next node
    public TreeNode next() {
        while (curt != null) {
            stack.push(curt);
            curt = curt.left;
        }
        
        curt = stack.pop();
        TreeNode node = curt;
        curt = curt.right;
        
        return node;
    }
}

http://www.cnblogs.com/yuzhangcmu/p/4197346.html
Python code:
http://bookshadow.com/weblog/2014/12/31/leetcode-binary-search-tree-iterator/
Implement In-order Iterator for Binary Tree
http://n00tc0d3r.blogspot.com/2013/08/implement-iterator-for-binarytree-i-in.html
public class InOrderBinaryTreeIteratorImpl implements InOrderBinaryTreeIterator {
   Stack<TreeNode> stack = new Stack<TreeNode>();
 
   /** Push node cur and all of its left children into stack */
   private void pushLeftChildren(TreeNode cur) {
     while (cur != null) {
       stack.push(cur);
       cur = cur.left;
     }
   }

   public InOrderBinaryTreeIterator(TreeNode root) {
     pushLeftChildren(root);
   }
   public boolean hasNext() {
     return !stack.isEmpty();
   }
   public Integer next() {
     if (!hasNext()) {
       throw new NoSuchElementException("All nodes have been visited!");
     }
 
     TreeNode res = stack.pop();
     pushLeftChildren(res.right);
 
     return res.val;
   }
   public void remove() {
     throw new UnsupportedOperationException("remove() is not supported.");
   }
 }

  public ArrayList<Integer> inorderTraversal(TreeNode root) {
   InOrderBinaryTreeIterator iterator = new InOrderBinaryTreeIteratorImpl(root);
   ArrayList<Integer> results = new ArrayList<Integer>();
   while (iterator.hasNext()) {
     results.add(iterator.next());
   }
   return results;  
 }

X. O(1) space and O(1) amortized time, using Morris Tree Traversal
https://leetcode.com/discuss/58469/solution-space-amortized-time-using-morris-tree-traversal
https://leetcode.com/discuss/23721/morris-traverse-solution

Construct Period

The idea is use in-order Morris Tree Traversal (check out [1][2] if you are not familiar with it, otherwise the bellow explanation to you is nonsense) to construct a threaded binary tree in construct function. (This is O(n) time, but we don't care much about it.) Then set a pointer (we call it "curr") to the smallest TreeNode, which is easy to do, just find the left-most child from root.

hasNext()

For hasNext() function, simple return "curr != null", which is by definition of threaded binary tree.

next()

For next() function, it is a little bit tricky. We call the right child of "curr" as "next". If "next" is not a normal right child of "curr", which means the right child relationship is constructed during the threaded binary tree construction period, then the next TreeNode we should iterate is indeed "next". However, if "next" is a normal right child of "curr", then the next TreeNode we should iterate is actually the left-most child of "next".

So the problem reduces to how to make clear the situation. Well, it is no hard. If "next" is null, then we've done, simply set "curr" to null. If "next" has no left child, or "next"'s left child is strictly larger than "curr", that means it is a normal right child of "curr", so we should set "curr" to left-most child of "next". Otherwise, we set "curr" to "next", and break the right child relationship between "curr" and "next", to recover the original tree structure.

Complexity analysis

The space complexity is straightforwardly O(1). The time complexity needs some more explanation. Since the only part that is not O(1) is when we search the left-most child of "next". However, for all the children along this left path (say, there are N children), we do once search left-most and (N-1) times simply go to right child. So the amortized time complexity is still O(1).

public class BSTIterator { private TreeNode curr; public BSTIterator(TreeNode root) { TreeNode prev; //Do a morris in-order traversal, to construct a threaded binary tree curr = root; while(curr != null){ if(curr.left == null){ curr = curr.right; } else{ prev = curr.left; while(prev.right != null && prev.right != curr) prev = prev.right; if(prev.right == null){ prev.right = curr; curr = curr.left; } else{ curr = curr.right; } } } //get the left-most child of root, i.e. the smallest TreeNode curr = root; while(curr != null && curr.left != null) curr = curr.left; } /** @return whether we have a next smallest number */ public boolean hasNext() { return curr != null; } /** @return the next smallest number */ public int next() { //copy the value we need to return int result = curr.val; TreeNode next = curr.right; if(next == null) curr = next; //the right child relationship is a normal one, find left-most //child of "next" else if(next.left == null || next.left.val > curr.val){ curr = next; while(curr.left != null) curr = curr.left; } //the right child relationship is made when we //construct the threaded binary tree else{ curr.right = null;//we recover the original tree structure curr = next; } return result; } }