Sponsored
Sponsored
This approach involves using a stack to simulate the in-order traversal of a binary search tree (BST). The stack is used to keep track of nodes to visit next, starting from the leftmost node (the smallest element). Each time next() is called, the stack pops one node, processes it, and then adds right child nodes to the stack to maintain the in-order sequence. This approach takes advantage of the tree's properties to efficiently traverse it.
Time Complexity: The average time complexity is O(1) for next() and hasNext() methods, though next() can take up to O(h) time in the worst case, where h is the height of the tree.
Space Complexity: O(h) due to the depth of the stack, where h is the height of the tree.
1import java.util.Stack;
2
3class BSTIterator {
4 private Stack<TreeNode> stack;
5
6 public BSTIterator(TreeNode root) {
7 stack = new Stack<>();
8 pushLeftNodes(root);
9 }
10
11 private void pushLeftNodes(TreeNode node) {
12 while (node != null) {
13 stack.push(node);
14 node = node.left;
15 }
16 }
17
18 public boolean hasNext() {
19 return !stack.isEmpty();
20 }
21
22 public int next() {
23 TreeNode node = stack.pop();
24 int result = node.val;
25 if (node.right != null) {
26 pushLeftNodes(node.right);
27 }
28 return result;
29 }
30}
31This Java solution leverages the Stack class for its internal stack implementation. The constructor pre-fills the stack with left-path nodes from the root. `next()` pops the stack to get the next smallest element and processes any right subtree by adding its left children to the stack. hasNext() checks the stack to see if more elements remain.
Morris Traversal is an in-order tree traversal technique that doesn't require stack or recursion, thus using O(1) auxiliary space. It temporarily modifies the tree structure to maintain caching pointers, ensuring nodes are revisited as necessary. Once traversal completes, the tree reverts to its original form.
Time Complexity: O(1) on average, with O(n) total time for n nodes.
Space Complexity: O(1) without recourse to stack/recursion.
1class BSTIterator:
2 def __init__(self, root: TreeNode):
3 self.current = root
4
5 def hasNext(self) -> bool:
6 return self.current is not None
7
8 def next(self) -> int:
9 result = 0
10 while self.current:
11 if self.current.left is None:
12 result = self.current.val
13 self.current = self.current.right
14 break
15 else:
16 pred = self.findPredecessor(self.current)
17 if pred.right is None:
18 pred.right = self.current
19 self.current = self.current.left
20 else:
21 pred.right = None
22 result = self.current.val
23 self.current = self.current.right
24 break
25 return result
26
27 def findPredecessor(self, node: TreeNode) -> TreeNode:
28 pred = node.left
29 while pred.right is not None and pred.right != node:
30 pred = pred.right
31 return pred
32Using Morris Traversal in Python effects node examination in ascending form, enforcing necessary temporary link repairs afterward. `hasNext` confirms ongoing traversal potential, ensuring comprehensive exploration with bounded memory usage.