Question
Formatted question description: https://leetcode.ca/all/173.html
173 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.
Credits:
Special thanks to @ts for adding this problem and creating all test cases.
@tag-tree
Algorithm
The non-recursive form of the in-order traversal of the binary tree requires an additional definition of a stack to assist. The building rule of the binary search tree is left<root<right
, and the in-order traversal can extract all nodes from small to large.
Code
Java
-
import java.util.ArrayList; import java.util.Collections; import java.util.List; import java.util.Stack; public class Binary_Search_Tree_Iterator { /** * Definition for binary tree * public class TreeNode { * int val; * TreeNode left; * TreeNode right; * TreeNode(int x) { val = x; } * } */ public class BSTIterator { Stack<TreeNode> sk; // @note:@memorize: important feature, min is always going left branch to leaf public BSTIterator(TreeNode root) { sk = new Stack<>(); // all the way to leftmost leaf while (root != null) { sk.push(root); root = root.left; } } /** @return whether we have a next smallest number */ public boolean hasNext() { return !sk.isEmpty(); } /** @return the next smallest number */ public int next() { TreeNode minNode = sk.pop(); TreeNode current = minNode; // update stack, possible next time min is frmo its right-then-left branch if (current.right != null) { current = current.right; // same logic as in constructor while (current != null) { sk.push(current.left); current = current.left; } } return minNode.val; } } /** * Your BSTIterator will be called like this: * BSTIterator i = new BSTIterator(root); * while (i.hasNext()) v[f()] = i.next(); */ }
-
// OJ: https://leetcode.com/problems/binary-search-tree-iterator/ // Time: O(1) amortized // Space: O(H) class BSTIterator { private: stack<TreeNode*> s; void pushNodes(TreeNode *node) { while (node) { s.push(node); node = node->left; } } public: BSTIterator(TreeNode* root) { pushNodes(root); } int next() { auto node = s.top(); s.pop(); pushNodes(node->right); return node->val; } bool hasNext() { return s.size(); } };
-
# Definition for a binary tree node # class TreeNode(object): # def __init__(self, x): # self.val = x # self.left = None # self.right = None class BSTIterator(object): def __init__(self, root): """ :type root: TreeNode """ self.p = None self.stack = [] if root: self.stack.append((1, root)) def hasNext(self): """ :rtype: bool """ return len(self.stack) > 0 def next(self): """ :rtype: int """ stack = self.stack while stack: p = stack.pop() if not p[1]: continue if p[0] == 0: return p[1].val else: l = [] if p[1].right: l.append((1, p[1].right)) l.append((0, p[1])) if p[1].left: l.append((1, p[1].left)) stack.extend(l) # Your BSTIterator will be called like this: # i, v = BSTIterator(root), [] # while i.hasNext(): v.append(i.next())