173. Binary Search Tree Iterator Medium

1/**
2 * [173] Binary Search Tree Iterator
3 *
4 * Implement the BSTIterator class that represents an iterator over the <a href="https://en.wikipedia.org/wiki/Tree_traversal#In-order_(LNR)" target="_blank">in-order traversal</a> of a binary search tree (BST):
5 * 
6 * 	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.
7 * 	boolean hasNext() Returns true if there exists a number in the traversal to the right of the pointer, otherwise returns false.
8 * 	int next() Moves the pointer to the right, then returns the number at the pointer.
9 * 
10 * Notice that by initializing the pointer to a non-existent smallest number, the first call to next() will return the smallest element in the BST.
11 * 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.
12 *  
13 * Example 1:
14 * <img alt="" src="https://assets.leetcode.com/uploads/2018/12/25/bst-tree.png" style="width: 189px; height: 178px;" />
15 * Input
16 * ["BSTIterator", "next", "next", "hasNext", "next", "hasNext", "next", "hasNext", "next", "hasNext"]
17 * [[[7, 3, 15, null, null, 9, 20]], [], [], [], [], [], [], [], [], []]
18 * Output
19 * [null, 3, 7, true, 9, true, 15, true, 20, false]
20 * Explanation
21 * BSTIterator bSTIterator = new BSTIterator([7, 3, 15, null, null, 9, 20]);
22 * bSTIterator.next();    // return 3
23 * bSTIterator.next();    // return 7
24 * bSTIterator.hasNext(); // return True
25 * bSTIterator.next();    // return 9
26 * bSTIterator.hasNext(); // return True
27 * bSTIterator.next();    // return 15
28 * bSTIterator.hasNext(); // return True
29 * bSTIterator.next();    // return 20
30 * bSTIterator.hasNext(); // return False
31 * 
32 *  
33 * Constraints:
34 * 
35 * 	The number of nodes in the tree is in the range [1, 10^5].
36 * 	0 <= Node.val <= 10^6
37 * 	At most 10^5 calls will be made to hasNext, and next.
38 * 
39 *  
40 * Follow up:
41 * 
42 * 	Could you implement next() and hasNext() to run in average O(1) time and use O(h) memory, where h is the height of the tree?
43 * 
44 */
45pub struct Solution {}
46use crate::util::tree::{TreeNode, to_tree};
47
48// problem: https://leetcode.com/problems/binary-search-tree-iterator/
49// discuss: https://leetcode.com/problems/binary-search-tree-iterator/discuss/?currentPage=1&orderBy=most_votes&query=
50
51// submission codes start here
52
53// Definition for a binary tree node.
54// #[derive(Debug, PartialEq, Eq)]
55// pub struct TreeNode {
56//   pub val: i32,
57//   pub left: Option<Rc<RefCell<TreeNode>>>,
58//   pub right: Option<Rc<RefCell<TreeNode>>>,
59// }
60// 
61// impl TreeNode {
62//   #[inline]
63//   pub fn new(val: i32) -> Self {
64//     TreeNode {
65//       val,
66//       left: None,
67//       right: None
68//     }
69//   }
70// }
71struct BSTIterator {
72        vec![]
73    }
74
75
76/** 
77 * `&self` means the method takes an immutable reference.
78 * If you need a mutable reference, change it to `&mut self` instead.
79 */
80impl BSTIterator {
81
82    fn new(root: Option<Rc<RefCell<TreeNode>>>) -> Self {
83        
84    }
85    
86    fn next(&self) -> i32 {
87        
88    }
89    
90    fn has_next(&self) -> bool {
91        
92    }
93}
94
95/**
96 * Your BSTIterator object will be instantiated and called as such:
97 * let obj = BSTIterator::new(root);
98 * let ret_1: i32 = obj.next();
99 * let ret_2: bool = obj.has_next();
100 */
101
102// submission codes end
103
104#[cfg(test)]
105mod tests {
106    use super::*;
107
108    #[test]
109    fn test_173() {
110    }
111}
112