binary_search_tree_iterator
1from utils import TreeNode 2from typing import Optional 3 4 5# @leet start 6class BSTIterator: 7 """ 8 This question asks us to define a binary search tree iterator. We can 9 do this by traversing the tree and then collecting all of the results 10 into an array, and indexing into it, checking if the pointer is in or 11 out of bounds. However, this takes $O(n)$ time, so it's memory expensive. 12 We can do this in $O(h)$ memory if we use an iterable. Unfortunately, 13 python doesn't have the ability to peek an iterable, unless you use 14 `more_itertools` which leetcode doesn't support, so we can do it the old 15 fashioned way of traversing the tree first and then calculating its length 16 and then making an iterable. 17 """ 18 19 def __init__(self, root: Optional[TreeNode]): 20 self.len = 0 21 self.i = -1 22 23 def get_len(node): 24 if not node: 25 return 26 self.len += 1 27 get_len(node.left) 28 get_len(node.right) 29 30 get_len(root) 31 32 def traverse(node): 33 if not node: 34 return 35 yield from traverse(node.left) 36 yield node.val 37 yield from traverse(node.right) 38 39 self.inorder = traverse(root) 40 41 def next(self) -> int: 42 self.i += 1 43 return next(self.inorder) 44 45 def hasNext(self) -> bool: 46 return self.i < self.len - 1 47 48 49# Your BSTIterator object will be instantiated and called as such: 50# obj = BSTIterator(root) 51# param_1 = obj.next() 52# param_2 = obj.hasNext() 53# @leet end 54 55 56def test(): 57 assert 2 + 2 == 4
class
BSTIterator:
7class BSTIterator: 8 """ 9 This question asks us to define a binary search tree iterator. We can 10 do this by traversing the tree and then collecting all of the results 11 into an array, and indexing into it, checking if the pointer is in or 12 out of bounds. However, this takes $O(n)$ time, so it's memory expensive. 13 We can do this in $O(h)$ memory if we use an iterable. Unfortunately, 14 python doesn't have the ability to peek an iterable, unless you use 15 `more_itertools` which leetcode doesn't support, so we can do it the old 16 fashioned way of traversing the tree first and then calculating its length 17 and then making an iterable. 18 """ 19 20 def __init__(self, root: Optional[TreeNode]): 21 self.len = 0 22 self.i = -1 23 24 def get_len(node): 25 if not node: 26 return 27 self.len += 1 28 get_len(node.left) 29 get_len(node.right) 30 31 get_len(root) 32 33 def traverse(node): 34 if not node: 35 return 36 yield from traverse(node.left) 37 yield node.val 38 yield from traverse(node.right) 39 40 self.inorder = traverse(root) 41 42 def next(self) -> int: 43 self.i += 1 44 return next(self.inorder) 45 46 def hasNext(self) -> bool: 47 return self.i < self.len - 1
This question asks us to define a binary search tree iterator. We can
do this by traversing the tree and then collecting all of the results
into an array, and indexing into it, checking if the pointer is in or
out of bounds. However, this takes $O(n)$ time, so it's memory expensive.
We can do this in $O(h)$ memory if we use an iterable. Unfortunately,
python doesn't have the ability to peek an iterable, unless you use
more_itertools which leetcode doesn't support, so we can do it the old
fashioned way of traversing the tree first and then calculating its length
and then making an iterable.
BSTIterator(root: Optional[utils.TreeNode])
20 def __init__(self, root: Optional[TreeNode]): 21 self.len = 0 22 self.i = -1 23 24 def get_len(node): 25 if not node: 26 return 27 self.len += 1 28 get_len(node.left) 29 get_len(node.right) 30 31 get_len(root) 32 33 def traverse(node): 34 if not node: 35 return 36 yield from traverse(node.left) 37 yield node.val 38 yield from traverse(node.right) 39 40 self.inorder = traverse(root)
def
test():