LeetCode 173. Binary Search Tree Iterator

December 14, 2024

Here are two solutions. One is recursive and the other iterative. The iterative solution is better as it can handle larger inputs.

Solution

Recursive

1from collections import deque
2# Definition for a binary tree node.
3# class TreeNode:
4#     def __init__(self, val=0, left=None, right=None):
5#         self.val = val
6#         self.left = left
7#         self.right = right
8class BSTIterator:
9
10    def __init__(self, root: Optional[TreeNode]):
11        self.nodes = deque([])
12
13        def traverse(node):
14            if not node:
15                return
16            
17            traverse(node.left)
18            self.nodes.append(node.val)
19            traverse(node.right)
20        
21        traverse(root)
22        
23
24    def next(self) -> int:
25        return self.nodes.popleft()
26
27    def hasNext(self) -> bool:
28        return len(self.nodes) > 0
29
30
31# Your BSTIterator object will be instantiated and called as such:
32# obj = BSTIterator(root)
33# param_1 = obj.next()
34# param_2 = obj.hasNext()

Time complexity is O(n) = n and space complexity is O(h).

iterative

1from collections import deque
2# Definition for a binary tree node.
3# class TreeNode:
4#     def __init__(self, val=0, left=None, right=None):
5#         self.val = val
6#         self.left = left
7#         self.right = right
8class BSTIterator:
9
10    def __init__(self, root: Optional[TreeNode]):
11        self.nodes = []
12        self.pushAll(root)      
13
14    def next(self) -> int:
15        node = self.nodes.pop()
16        self.pushAll(node.right)
17        return node.val
18
19    def hasNext(self) -> bool:
20        return len(self.nodes) > 0
21    
22    def pushAll(self, node):
23        while node:
24            self.nodes.append(node)
25            node = node.left
26
27
28
29# Your BSTIterator object will be instantiated and called as such:
30# obj = BSTIterator(root)
31# param_1 = obj.next()
32# param_2 = obj.hasNext()

LeetCode 103. Binary Tree Zigzag Level Order Traversal

LeetCode 133. Clone Graph