next() and prev(). This allows O(1) time for all operations after the initial traversal.

Approach

Do an inorder traversal of the BST and store the values in a list.
Use an index pointer to track the current position.
next() increments the pointer and returns the value.
prev() decrements the pointer and returns the value.
hasNext() and hasPrev() check pointer bounds.

Code

[{"language":"C++","code":"class BSTIterator {\n    vector<int> vals;\n    int idx;\n    void inorder(TreeNode* node) {\n        if (!node) return;\n        inorder(node->left);\n        vals.push_back(node->val);\n        inorder(node->right);\n    }\npublic:\n    BSTIterator(TreeNode* root) : idx(-1) {\n        inorder(root);\n    }\n    bool hasNext() { return idx + 1 < (int)vals.size(); }\n    int next() { return vals[++idx]; }\n    bool hasPrev() { return idx > 0; }\n    int prev() { return vals[--idx]; }\n};","lang":"cpp","html":"<pre class=\"shiki shiki-themes github-light github-dark\" style=\"background-color:#fff;--shiki-dark-bg:#24292e;color:#24292e;--shiki-dark:#e1e4e8\" tabindex=\"0\"><code><span class=\"line\"><span style=\"color:#D73A49;--shiki-dark:#F97583\">class</span><span style=\"color:#6F42C1;--shiki-dark:#B392F0\"> BSTIterator</span><span style=\"color:#24292E;--shiki-dark:#E1E4E8\"> {</span></span>\n<span class=\"line\"><span style=\"color:#24292E;--shiki-dark:#E1E4E8\">    vector</span><span style=\"color:#D73A49;--shiki-dark:#F97583\">&#x3C;int></span><span style=\"color:#24292E;--shiki-dark:#E1E4E8\"> vals;</span></span>\n<span class=\"line\"><span style=\"color:#D73A49;--shiki-dark:#F97583\">    int</span><span style=\"color:#24292E;--shiki-dark:#E1E4E8\"> idx;</span></span>\n<span class=\"line\"><span style=\"color:#D73A49;--shiki-dark:#F97583\">    void</span><span style=\"color:#6F42C1;--shiki-dark:#B392F0\"> inorder</span><span style=\"color:#24292E;--shiki-dark:#E1E4E8\">(</span><span style=\"color:#6F42C1;--shiki-dark:#B392F0\">TreeNode</span><span style=\"color:#D73A49;--shiki-dark:#F97583\">*</span><span style=\"color:#E36209;--shiki-dark:#FFAB70\"> node</span><span style=\"color:#24292E;--shiki-dark:#E1E4E8\">) {</span></span>\n<span class=\"line\"><span style=\"color:#D73A49;--shiki

Related Tags