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.
1#include <stack>
2
3class BSTIterator {
4public:
5 BSTIterator(TreeNode* root) {
6 pushLeftNodes(root);
7 }
8
9 bool hasNext() {
10 return !stk.empty();
11 }
12
13 int next() {
14 TreeNode* node = stk.top();
15 stk.pop();
int result = node->val;
if (node->right) {
pushLeftNodes(node->right);
}
return result;
}
private:
std::stack<TreeNode*> stk;
void pushLeftNodes(TreeNode* node) {
while (node) {
stk.push(node);
node = node->left;
}
}
};
The C++ solution leverages the standard stack library for implementing the BSTIterator. The constructor initializes the stack with left children starting from the root. The `next` method processes the current node, getting the smallest element, moves the pointer, and handles right children, ensuring the traversal remains in order. The `hasNext` method simply checks the stack's state to decide if further traversals are possible.
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.
The C solution utilizes Morris traversal to achieve an in-order sequence without extra space. The iterator temporarily modifies the tree with connections called threads to track nodes. As the `next` method works through the tree, each accessed node prints its value and advances by fixing connections afterward. The `hasNext` method merely checks if the tree traversal has completed.