{"id":"2e499af1-5b63-411a-9f34-e7b7c7aa89ad","name":"Binary Search Tree Iterator 2","description":"1. Implement the BSTIterator class that represents an iterator over the in-order traversal of a binary search tree (BST):\r\n\r\n2. BSTIterator(TreeNode root) Initializes an object of the BSTIterator class. The root of the BST is given as part of the constructor. The pointer should be initialized to a non-existent number smaller than any element in the BST.\r\nboolean hasNext() Returns true if there exists a number in the traversal to the right of the pointer, otherwise returns false.\r\nint next() Moves the pointer to the right, then returns the number at the pointer.\r\n\r\n3. You may assume that next() calls will always be valid. That is, there will be at least a next number in the in-order traversal when next() is called.\r\n","inputFormat":"Input is managed for you.\r\n","outputFormat":"Output is managed for you. \r\n","constraints":"1. The number of nodes in the tree is in the range [1, 105].\r\n2. 0 &lt;= Node.val &lt;= 106\r\n3. At most 105 calls will be made to hasNext, and next.\r\n","sampleCode":{"cpp":{"code":"#include <iostream>\r\n#include <vector>\r\n#include <stack>\r\nusing namespace std;\r\n\r\nclass TreeNode\r\n{\r\npublic:\r\n int val = 0;\r\n TreeNode* left = nullptr;\r\n TreeNode* right = nullptr;\r\n\r\n TreeNode(int val)\r\n {\r\n this->val = val;\r\n }\r\n};\r\n\r\nclass BSTIterator\r\n{\r\npublic:\r\n BSTIterator(TreeNode* root)\r\n {\r\n }\r\n\r\n int next()\r\n {\r\n }\r\n\r\n bool hasNext()\r\n {\r\n }\r\n};\r\n\r\n// input_Section_====================================================================\r\n\r\nvoid display(TreeNode* node)\r\n{\r\n if (node == nullptr)\r\n return;\r\n\r\n string str = \"\";\r\n str += ((node->left != nullptr ? to_string(node->left->val) : \".\"));\r\n str += (\" -> \" + to_string(node->val) + \" <- \");\r\n str += ((node->right != nullptr ? to_string(node->right->val) : \".\"));\r\n\r\n cout << str << endl;\r\n\r\n display(node->left);\r\n display(node->right);\r\n}\r\n\r\nTreeNode* buildTree(vector<int>& inOrder, int si, int ei)\r\n{\r\n if (si > ei)\r\n return nullptr;\r\n\r\n int mid = (si + ei) / 2;\r\n TreeNode* node = new TreeNode(inOrder[mid]);\r\n\r\n node->left = buildTree(inOrder, si, mid - 1);\r\n node->right = buildTree(inOrder, mid + 1, ei);\r\n\r\n return node;\r\n}\r\n\r\nTreeNode* constructFromInOrder(vector<int>& in)\r\n{\r\n int n = in.size();\r\n return buildTree(in, 0, n - 1);\r\n}\r\n\r\nvoid solve()\r\n{\r\n int n;\r\n cin >> n;\r\n vector<int> in(n, 0);\r\n for (int i = 0; i < n; i++)\r\n {\r\n cin >> in[i];\r\n }\r\n\r\n TreeNode* root = constructFromInOrder(in);\r\n BSTIterator itr(root);\r\n while (itr.hasNext())\r\n {\r\n cout << (itr.next()) << endl;\r\n }\r\n}\r\n\r\nint main()\r\n{\r\n solve();\r\n return 0;\r\n}"},"java":{"code":"import java.util.Scanner;\r\nimport java.util.LinkedList;\r\n\r\npublic class Main {\r\n public static Scanner scn = new Scanner(System.in);\r\n\r\n public static class TreeNode {\r\n int val = 0;\r\n TreeNode left = null;\r\n TreeNode right = null;\r\n\r\n TreeNode(int val) {\r\n this.val = val;\r\n }\r\n }\r\n\r\n public static class BSTIterator {\r\n public BSTIterator(TreeNode root) {\r\n\r\n }\r\n\r\n public int next() {\r\n\r\n }\r\n\r\n public boolean hasNext() {\r\n\r\n }\r\n }\r\n\r\n // input_section=================================================\r\n\r\n public static void display(TreeNode node) {\r\n if (node == null)\r\n return;\r\n\r\n StringBuilder sb = new StringBuilder();\r\n sb.append((node.left != null ? node.left.val : \".\"));\r\n sb.append(\" -> \" + node.val + \" <- \");\r\n sb.append((node.right != null ? node.right.val : \".\"));\r\n\r\n System.out.println(sb.toString());\r\n\r\n display(node.left);\r\n display(node.right);\r\n\r\n }\r\n\r\n public static TreeNode constructFromInOrder_(int[] in, int si, int ei) {\r\n if (si > ei)\r\n return null;\r\n\r\n int mid = (si + ei) / 2;\r\n TreeNode node = new TreeNode(in[mid]);\r\n\r\n node.left = constructFromInOrder_(in, si, mid - 1);\r\n node.right = constructFromInOrder_(in, mid + 1, ei);\r\n\r\n return node;\r\n }\r\n\r\n public static void solve() {\r\n int n = scn.nextInt();\r\n int[] in = new int[n];\r\n for (int i = 0; i < n; i++)\r\n in[i] = scn.nextInt();\r\n\r\n TreeNode root = constructFromInOrder_(in, 0, in.length - 1);\r\n BSTIterator itr = new BSTIterator(root);\r\n while (itr.hasNext()) {\r\n System.out.println(itr.next());\r\n }\r\n }\r\n\r\n public static void main(String[] args) {\r\n solve();\r\n }\r\n}"},"python":{"code":""}},"points":10,"difficulty":"easy","sampleInput":"7\r\n1 2 3 4 5 6 7","sampleOutput":"1\r\n2\r\n3\r\n4\r\n5\r\n6\r\n7\r\n","questionVideo":"","hints":[],"associated":[],"solutionSeen":false,"tags":[],"meta":{"path":[{"id":0,"name":"home"},{"id":"0c54b191-7b99-4f2c-acb3-e7f2ec748b2a","name":"Data Structures and Algorithms","slug":"data-structures-and-algorithms","type":0},{"id":"2e9df04c-be14-441c-9a18-8b5a8ca6596d","name":"Trees For Intermediate","slug":"trees-for-intermediate-9994","type":0},{"id":"f1002479-50ed-4b20-add5-612e567bcd61","name":"Binary Search Tree Iterator 2","slug":"binary-search-tree-iterator-2","type":1}],"next":{"id":"62d99993-0b91-44d6-a78b-c08247a7e61a","name":"Binary Search Tree Iterator 2","type":3,"slug":"binary-search-tree-iterator-2"},"prev":{"id":"9a1beca3-99c1-4dda-b571-dea3cce40fa9","name":"Top View of a binary tree","type":3,"slug":"top-view-of-a-binary-tree"}}}

Binary Search Tree Iterator 2

1. Implement the BSTIterator class that represents an iterator over the in-order traversal of a binary search tree (BST): 2. BSTIterator(TreeNode root) Initializes an object of the BSTIterator class. The root of the BST is given as part of the constructor. The pointer should be initialized to a non-existent number smaller than any element in the BST. boolean hasNext() Returns true if there exists a number in the traversal to the right of the pointer, otherwise returns false. int next() Moves the pointer to the right, then returns the number at the pointer. 3. You may assume that next() calls will always be valid. That is, there will be at least a next number in the in-order traversal when next() is called.

{"id":"2e499af1-5b63-411a-9f34-e7b7c7aa89ad","name":"Binary Search Tree Iterator 2","description":"1. Implement the BSTIterator class that represents an iterator over the in-order traversal of a binary search tree (BST):\r\n\r\n2. BSTIterator(TreeNode root) Initializes an object of the BSTIterator class. The root of the BST is given as part of the constructor. The pointer should be initialized to a non-existent number smaller than any element in the BST.\r\nboolean hasNext() Returns true if there exists a number in the traversal to the right of the pointer, otherwise returns false.\r\nint next() Moves the pointer to the right, then returns the number at the pointer.\r\n\r\n3. You may assume that next() calls will always be valid. That is, there will be at least a next number in the in-order traversal when next() is called.\r\n","inputFormat":"Input is managed for you.\r\n","outputFormat":"Output is managed for you. \r\n","constraints":"1. The number of nodes in the tree is in the range [1, 105].\r\n2. 0 &lt;= Node.val &lt;= 106\r\n3. At most 105 calls will be made to hasNext, and next.\r\n","sampleCode":{"cpp":{"code":"#include <iostream>\r\n#include <vector>\r\n#include <stack>\r\nusing namespace std;\r\n\r\nclass TreeNode\r\n{\r\npublic:\r\n int val = 0;\r\n TreeNode* left = nullptr;\r\n TreeNode* right = nullptr;\r\n\r\n TreeNode(int val)\r\n {\r\n this->val = val;\r\n }\r\n};\r\n\r\nclass BSTIterator\r\n{\r\npublic:\r\n BSTIterator(TreeNode* root)\r\n {\r\n }\r\n\r\n int next()\r\n {\r\n }\r\n\r\n bool hasNext()\r\n {\r\n }\r\n};\r\n\r\n// input_Section_====================================================================\r\n\r\nvoid display(TreeNode* node)\r\n{\r\n if (node == nullptr)\r\n return;\r\n\r\n string str = \"\";\r\n str += ((node->left != nullptr ? to_string(node->left->val) : \".\"));\r\n str += (\" -> \" + to_string(node->val) + \" <- \");\r\n str += ((node->right != nullptr ? to_string(node->right->val) : \".\"));\r\n\r\n cout << str << endl;\r\n\r\n display(node->left);\r\n display(node->right);\r\n}\r\n\r\nTreeNode* buildTree(vector<int>& inOrder, int si, int ei)\r\n{\r\n if (si > ei)\r\n return nullptr;\r\n\r\n int mid = (si + ei) / 2;\r\n TreeNode* node = new TreeNode(inOrder[mid]);\r\n\r\n node->left = buildTree(inOrder, si, mid - 1);\r\n node->right = buildTree(inOrder, mid + 1, ei);\r\n\r\n return node;\r\n}\r\n\r\nTreeNode* constructFromInOrder(vector<int>& in)\r\n{\r\n int n = in.size();\r\n return buildTree(in, 0, n - 1);\r\n}\r\n\r\nvoid solve()\r\n{\r\n int n;\r\n cin >> n;\r\n vector<int> in(n, 0);\r\n for (int i = 0; i < n; i++)\r\n {\r\n cin >> in[i];\r\n }\r\n\r\n TreeNode* root = constructFromInOrder(in);\r\n BSTIterator itr(root);\r\n while (itr.hasNext())\r\n {\r\n cout << (itr.next()) << endl;\r\n }\r\n}\r\n\r\nint main()\r\n{\r\n solve();\r\n return 0;\r\n}"},"java":{"code":"import java.util.Scanner;\r\nimport java.util.LinkedList;\r\n\r\npublic class Main {\r\n public static Scanner scn = new Scanner(System.in);\r\n\r\n public static class TreeNode {\r\n int val = 0;\r\n TreeNode left = null;\r\n TreeNode right = null;\r\n\r\n TreeNode(int val) {\r\n this.val = val;\r\n }\r\n }\r\n\r\n public static class BSTIterator {\r\n public BSTIterator(TreeNode root) {\r\n\r\n }\r\n\r\n public int next() {\r\n\r\n }\r\n\r\n public boolean hasNext() {\r\n\r\n }\r\n }\r\n\r\n // input_section=================================================\r\n\r\n public static void display(TreeNode node) {\r\n if (node == null)\r\n return;\r\n\r\n StringBuilder sb = new StringBuilder();\r\n sb.append((node.left != null ? node.left.val : \".\"));\r\n sb.append(\" -> \" + node.val + \" <- \");\r\n sb.append((node.right != null ? node.right.val : \".\"));\r\n\r\n System.out.println(sb.toString());\r\n\r\n display(node.left);\r\n display(node.right);\r\n\r\n }\r\n\r\n public static TreeNode constructFromInOrder_(int[] in, int si, int ei) {\r\n if (si > ei)\r\n return null;\r\n\r\n int mid = (si + ei) / 2;\r\n TreeNode node = new TreeNode(in[mid]);\r\n\r\n node.left = constructFromInOrder_(in, si, mid - 1);\r\n node.right = constructFromInOrder_(in, mid + 1, ei);\r\n\r\n return node;\r\n }\r\n\r\n public static void solve() {\r\n int n = scn.nextInt();\r\n int[] in = new int[n];\r\n for (int i = 0; i < n; i++)\r\n in[i] = scn.nextInt();\r\n\r\n TreeNode root = constructFromInOrder_(in, 0, in.length - 1);\r\n BSTIterator itr = new BSTIterator(root);\r\n while (itr.hasNext()) {\r\n System.out.println(itr.next());\r\n }\r\n }\r\n\r\n public static void main(String[] args) {\r\n solve();\r\n }\r\n}"},"python":{"code":""}},"points":10,"difficulty":"easy","sampleInput":"7\r\n1 2 3 4 5 6 7","sampleOutput":"1\r\n2\r\n3\r\n4\r\n5\r\n6\r\n7\r\n","questionVideo":"","hints":[],"associated":[],"solutionSeen":false,"tags":[],"meta":{"path":[{"id":0,"name":"home"},{"id":"0c54b191-7b99-4f2c-acb3-e7f2ec748b2a","name":"Data Structures and Algorithms","slug":"data-structures-and-algorithms","type":0},{"id":"2e9df04c-be14-441c-9a18-8b5a8ca6596d","name":"Trees For Intermediate","slug":"trees-for-intermediate-9994","type":0},{"id":"f1002479-50ed-4b20-add5-612e567bcd61","name":"Binary Search Tree Iterator 2","slug":"binary-search-tree-iterator-2","type":1}],"next":{"id":"62d99993-0b91-44d6-a78b-c08247a7e61a","name":"Binary Search Tree Iterator 2","type":3,"slug":"binary-search-tree-iterator-2"},"prev":{"id":"9a1beca3-99c1-4dda-b571-dea3cce40fa9","name":"Top View of a binary tree","type":3,"slug":"top-view-of-a-binary-tree"}}}
plane

Editor


Loading...

Binary Search Tree Iterator 2

easy

1. Implement the BSTIterator class that represents an iterator over the in-order traversal of a binary search tree (BST): 2. BSTIterator(TreeNode root) Initializes an object of the BSTIterator class. The root of the BST is given as part of the constructor. The pointer should be initialized to a non-existent number smaller than any element in the BST. boolean hasNext() Returns true if there exists a number in the traversal to the right of the pointer, otherwise returns false. int next() Moves the pointer to the right, then returns the number at the pointer. 3. You may assume that next() calls will always be valid. That is, there will be at least a next number in the in-order traversal when next() is called.

Constraints

1. The number of nodes in the tree is in the range [1, 105]. 2. 0 <= Node.val <= 106 3. At most 105 calls will be made to hasNext, and next.

Format

Input

Input is managed for you.

Output

Output is managed for you.

Example

Sample Input

7 1 2 3 4 5 6 7

Sample Output

1 2 3 4 5 6 7

Discussions

Show Discussion

Related Resources

related resources

Turning Off Zen Mode