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 <stdio.h>
2#include <stdlib.h>
3#include <stdbool.h>
4
5// TreeNode structure definition
6struct TreeNode {
7 int val;
8 struct TreeNode *left;
9 struct TreeNode *right;
10};
11
12// Stack structure definition
13typedef struct Stack {
14 struct TreeNode* node;
15 struct Stack* next;
16} Stack;
17
18// BSTIterator structure definition
19typedef struct {
20 Stack* top;
21} BSTIterator;
22
23// Function to create a new stack node
24Stack* newStackNode(struct TreeNode* node) {
25 Stack* stackNode = malloc(sizeof(Stack));
26 stackNode->node = node;
27 stackNode->next = NULL;
28 return stackNode;
29}
30
31// Function to push a node to the stack
32void push(Stack** topRef, struct TreeNode* node) {
33 Stack* stackNode = newStackNode(node);
34 stackNode->next = *topRef;
35 *topRef = stackNode;
36}
37
38// Function to pop a node from the stack
39struct TreeNode* pop(Stack** topRef) {
40 if (*topRef == NULL) return NULL;
41 Stack* top = *topRef;
42 *topRef = top->next;
43 struct TreeNode* node = top->node;
44 free(top);
45 return node;
46}
47
48// Function to push all left children of a node to the stack
49void pushLeftNodes(Stack** stack, struct TreeNode* node) {
50 while (node != NULL) {
51 push(stack, node);
52 node = node->left;
53 }
54}
55
56// Constructor for BSTIterator
57BSTIterator* bSTIteratorCreate(struct TreeNode* root) {
58 BSTIterator* iterator = malloc(sizeof(BSTIterator));
59 iterator->top = NULL;
60 pushLeftNodes(&iterator->top, root);
61 return iterator;
62}
63
64// Check if there's a next node
65bool bSTIteratorHasNext(BSTIterator* iterator) {
66 return iterator->top != NULL;
67}
68
69// Return the next smallest node
70int bSTIteratorNext(BSTIterator* iterator) {
71 struct TreeNode* node = pop(&iterator->top);
72 int result = node->val;
73 if (node->right != NULL) {
74 pushLeftNodes(&iterator->top, node->right);
75 }
76 return result;
77}
78
79// Destructor
80void bSTIteratorFree(BSTIterator* iterator) {
81 while (iterator->top != NULL) {
82 pop(&iterator->top);
83 }
84 free(iterator);
85}
86The C solution for the BSTIterator uses a stack implemented as a linked list with basic stack operations like push and pop. The constructor initializes the stack with all left children of the root node. The `next` function pops the top of the stack, processes the node, and pushes any right child nodes' left children. The `hasNext` function checks if there are elements in the stack, indicating if another call to `next` is valid.
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.
1#include <stdlib.h>
2#include <stdbool.h>
3
4// TreeNode structure definition
5struct TreeNode {
6 int val;
7 struct TreeNode *left;
8 struct TreeNode *right;
9};
10
11// BSTIterator structure definition
12typedef struct {
13 struct TreeNode* current;
14} BSTIterator;
15
16// Constructor for BSTIterator
17BSTIterator* bSTIteratorCreate(struct TreeNode* root) {
18 BSTIterator* iterator = (BSTIterator*)malloc(sizeof(BSTIterator));
19 iterator->current = root;
20 return iterator;
21}
22
23// Function to find the rightmost node in the left subtree
24struct TreeNode* findPredecessor(struct TreeNode* node) {
25 struct TreeNode* pred = node->left;
26 while (pred->right && pred->right != node) {
27 pred = pred->right;
28 }
29 return pred;
30}
31
32// Check if there's a next node
33bool bSTIteratorHasNext(BSTIterator* iterator) {
34 return iterator->current != NULL;
35}
36
37// Return the next smallest node
38int bSTIteratorNext(BSTIterator* iterator) {
39 int result = 0;
40 while (iterator->current) {
41 if (iterator->current->left == NULL) {
42 result = iterator->current->val;
43 iterator->current = iterator->current->right;
44 return result;
45 }
46
47 struct TreeNode* pred = findPredecessor(iterator->current);
48
49 if (pred->right == NULL) {
50 pred->right = iterator->current;
51 iterator->current = iterator->current->left;
52 } else {
53 pred->right = NULL;
54 result = iterator->current->val;
55 iterator->current = iterator->current->right;
56 return result;
57 }
58 }
59 return result; // This line may not be necessary because iteration always has next
60}
61
62// Destructor
63void bSTIteratorFree(BSTIterator* iterator) {
64 free(iterator);
65}
66The 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.