BinarySearch 0762 Binary Search Tree Iterator Sequel

Problem statement

https://binarysearch.com/problems/Binary-Search-Tree-Iterator-Sequel/

Solution

Equal to Leetcode 1586 Binary Search Tree Iterator II.

Complexity

Time complexity if init is O(n), all others are O(1).

Code

class BSTIterator:
    def __init__(self, root):
        def dfs(node):
            if not node: return []
            return dfs(node.left) + [node.val] + dfs(node.right)
        self.arr = dfs(root)
        self.size = len(self.arr)
        self.idx = - 1

    def hasnext(self):
        return self.idx < self.size - 1

    def next(self):
        self.idx += 1
        return self.arr[self.idx]
        
    def hasprev(self):
        return self.idx > 0

    def prev(self):
        self.idx -= 1
        return self.arr[self.idx]