SWE Interview preparation

https://leetcode.com/problems/range-sum-of-bst/ Given the  root  node of a binary search tree, return the sum of values of all nodes with value between  L  and  R  (inclusive). The binary search tree is guaranteed to have unique values. Example 1: Input: root = [10,5,15,3,7,null,18] , L = 7 , R = 15 Output: 32 Example 2: Input: root = [10,5,15,3,7,13,18,1,null,6] , L = 6 , R = 10 Output: 23 Note: The number of nodes in the tree is at most  10000 . The final answer is guaranteed to be less than  2^31 . --- Intuition We need to cover all nodes - simple dfs with check at each node is trivial - O(n) We can use the info that this is BST If current node val >=L => dfs (node.left) if current node val <= R => dfs (node.right) --- Time - O(R - L) ~ O(N) Space - O(1) ---

https://leetcode.com/problems/binary-search-tree-iterator/ Implement an iterator over a binary search tree (BST). Your iterator will be initialized with the root node of a BST. Calling  next()  will return the next smallest number in the BST. Example: BSTIterator iterator = new BSTIterator(root); iterator.next(); // return 3 iterator.next(); // return 7 iterator.hasNext(); // return true iterator.next(); // return 9 iterator.hasNext(); // return true iterator.next(); // return 15 iterator.hasNext(); // return true iterator.next(); // return 20 iterator.hasNext(); // return false Note: next()  and  hasNext()  should run in average O(1) time and uses O( h ) memory, where  h  is the height of the tree. You may assume that  next()  call will always be valid, that is, there will be at least a next smallest number in the BST when  next()  is called. --- Intuition Saving in order traversal in arra...