[173. Binary Search Tree Iterator](https://leetcode.com/problems/binary-search-tree-iterator/)

--- tags: leetcode --- # [173. Binary Search Tree Iterator](https://leetcode.com/problems/binary-search-tree-iterator/) --- # My Solution ## Solution 1 ### The Key Idea for Solving This Coding Question Use DFS (recursion) to flatten all the node values into an array. ### C++ Code ```cpp= /** * Definition for a binary tree node. * struct TreeNode { * int val; * TreeNode *left; * TreeNode *right; * TreeNode() : val(0), left(nullptr), right(nullptr) {} * TreeNode(int x) : val(x), left(nullptr), right(nullptr) {} * TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {} * }; */ class BSTIterator { public: BSTIterator(TreeNode *root) : idx(0) { dfs(root); } bool hasNext() { return idx < inorder.size(); } int next() { return inorder[idx++]; } private: vector<int> inorder; int idx; void dfs(TreeNode *root) { if (root == nullptr) { return; } dfs(root->left); inorder.push_back(root->val); dfs(root->right); } }; /** * Your BSTIterator object will be instantiated and called as such: * BSTIterator* obj = new BSTIterator(root); * int param_1 = obj->next(); * bool param_2 = obj->hasNext(); */ ``` ### Time Complexity: * `BSTIterator` $O(n)$ $n$ is the number of nodes in BST. * `hasNext` $O(1)$ * `next` $O(1)$ ### Space Complexity: * `BSTIterator` $O(H)$ $H$ is the height of the BST. * `hasNext` $O(1)$ * `next` $O(1)$ ## Solution 2 ### The Key Idea for Solving This Coding Question Use DFS (iteration with stack) to partitially traverse the BST. ### C++ Code ```cpp= /** * Definition for a binary tree node. * struct TreeNode { * int val; * TreeNode *left; * TreeNode *right; * TreeNode() : val(0), left(nullptr), right(nullptr) {} * TreeNode(int x) : val(x), left(nullptr), right(nullptr) {} * TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {} * }; */ class BSTIterator { public: BSTIterator(TreeNode *root) { dfs(root); } bool hasNext() { return !st.empty(); } int next() { TreeNode *node = st.top(); st.pop(); dfs(node->right); return node->val; } private: stack<TreeNode *> st; void dfs(TreeNode *root) { while(root != nullptr) { st.push(root); root = root->left; } } }; /** * Your BSTIterator object will be instantiated and called as such: * BSTIterator* obj = new BSTIterator(root); * int param_1 = obj->next(); * bool param_2 = obj->hasNext(); */ ``` ### Time Complexity: * `BSTIterator` $O(H)$ $H$ is the height of the BST. * `hasNext` $O(1)$ * `next` $O(H)$ ### Space Complexity: * `BSTIterator` $O(H)$ * `hasNext` $O(1)$ * `next` $O(H)$ ## Solution 3 ### The Key Idea for Solving This Coding Question Convert BST to a sorted linked list by Morris Traversal. ### C++ Code ```cpp= /** * Definition for a binary tree node. * struct TreeNode { * int val; * TreeNode *left; * TreeNode *right; * TreeNode() : val(0), left(nullptr), right(nullptr) {} * TreeNode(int x) : val(x), left(nullptr), right(nullptr) {} * TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {} * }; */ class BSTIterator { public: BSTIterator(TreeNode *root) : head(nullptr) { dfs(root); } bool hasNext() { return head != nullptr; } int next() { int rev = head->val; head = head->right; return rev; } private: TreeNode *head; void dfs(TreeNode *root) { TreeNode *predecessor = nullptr; while (root != nullptr) { if (root->left == nullptr) { if (head == nullptr) { head = root; } predecessor = root; root = root->right; } else { TreeNode *node = root->left; while (node->right != nullptr && node->right != root) { node = node->right; } if (node->right == nullptr) { node->right = root; TreeNode *x = root; root = root->left; x->left = nullptr; if (predecessor != nullptr) { predecessor->right = root; } } // else { // // In morris traversal, this else-branch is for restoring // // the tree structure. However, we need to keep root->right // // pointing to root's successor, so this branch is not used. // // Also, the left pointer of root's successor has been set // // to nullptr, so this branch won't be run. // root = root->right; // node->right = nullptr; //} } } // end of while-loop } }; /** * Your BSTIterator object will be instantiated and called as such: * BSTIterator* obj = new BSTIterator(root); * int param_1 = obj->next(); * bool param_2 = obj->hasNext(); */ ``` ### Time Complexity: * `BSTIterator` $O(n)$ $n$ is the number of nodes in BST. * `hasNext`: $O(1)$ * `next` $O(1)$ ### Space Complexity: * `BSTIterator` $O(1)$ * `hasNext` $O(1)$ * `next` $O(1)$ # Miscellaneous