Binary Search Tree Iterator II — LeetCode 1586 Python Solution
MediumLeetCode PremiumStackTreeDesignBinary Search TreeBinary TreeIterator
- Problem
- #1586
- Pattern
- Stack
- Reading time
- 8 min
- Source
- leetcode.com
The problem
Implement the BSTIterator class that represents an iterator over the in-order traversal of a binary search tree (BST): BSTIterator(TreeNode root) Initializes an object of the BSTIterator class. The root of the BST is given as part of the constructor.
Example
- Input
- ["BSTIterator", "next", "next", "prev", "next", "hasNext", "next", "next", "next", "hasNext", "hasPrev", "prev", "prev"]
- Output
- [null, 3, 7, 3, 7, true, 9, 15, 20, false, true, 15, 9]
- Explanation
- // The underlined element is where the pointer currently is.
Python solution
Python
# Definition for a binary tree node.
# class TreeNode:
# def __init__(self, val=0, left=None, right=None):
# self.val = val
# self.left = left
# self.right = right
class BSTIterator:
def __init__(self, root: Optional[TreeNode]):
self.nums = []
def dfs(root):
if root is None:
return
dfs(root.left)
self.nums.append(root.val)
dfs(root.right)
dfs(root)
self.i = -1
def hasNext(self) -> bool:
return self.i < len(self.nums) - 1
def next(self) -> int:
self.i += 1
return self.nums[self.i]
def hasPrev(self) -> bool:
return self.i > 0
def prev(self) -> int:
self.i -= 1
return self.nums[self.i]
# Your BSTIterator object will be instantiated and called as such:
# obj = BSTIterator(root)
# param_1 = obj.hasNext()
# param_2 = obj.next()
# param_3 = obj.hasPrev()
# param_4 = obj.prev()Complexity
| Measure | Complexity |
|---|---|
| Time | O(n) |
| Space | O(n) auxiliary |
Pattern: Stack
When the most recent unresolved thing is the one that matters, use a stack. LeetCode 1586. Binary Search Tree Iterator II is filed here on both counts: the reference solution below belongs to the algorithm family this hub collects, and LeetCode tags it Stack.
The stack guide has the Python template for the pattern and the 194 LeetCode problems that use it.
Related problems
Frequently asked questions
- How hard is LeetCode 1586. Binary Search Tree Iterator II?
- LeetCode 1586. Binary Search Tree Iterator II is rated Medium on LeetCode.
- What is the time complexity of LeetCode 1586. Binary Search Tree Iterator II?
- The Python solution on this page runs in O(n).
- What is the space complexity of LeetCode 1586. Binary Search Tree Iterator II?
- The Python solution on this page uses O(n) auxiliary space.
- What topics does LeetCode 1586. Binary Search Tree Iterator II cover?
- LeetCode 1586. Binary Search Tree Iterator II is tagged Stack, Tree, Design, Binary Search Tree, Binary Tree and Iterator on LeetCode.
- Is LeetCode 1586. Binary Search Tree Iterator II a premium problem?
- Yes. LeetCode 1586. Binary Search Tree Iterator II is a LeetCode Premium problem, so the full statement and test cases require a paid LeetCode subscription.