SWE Interview preparation

 https://leetcode.com/problems/inorder-successor-in-bst-ii/description/ Given a  node  in a binary search tree, return  the in-order successor of that node in the BST . If that node has no in-order successor, return  null . The successor of a  node  is the node with the smallest key greater than  node.val . You will have direct access to the node but not to the root of the tree. Each node will have a reference to its parent node. Below is the definition for  Node : class Node { public int val; public Node left; public Node right; public Node parent; }   Example 1: Input: tree = [2,1,3], node = 1 Output: 2 Explanation: 1's in-order successor node is 2. Note that both the node and the return value is of Node type. Example 2: Input: tree = [5,3,6,2,4,null,null,1], node = 6 Output: null Explanation: There is no in-order successor of the current node, so the answer is null.   Constraints: The number of nodes in the ...

https://leetcode.com/problems/inorder-successor-in-bst/ https://github.com/openset/leetcode/tree/master/problems/inorder-successor-in-bst https://www.lintcode.com/problem/inorder-successor-in-bst/description Given a binary search tree and a node in it, find the in-order successor of that node in the BST. The successor of a node  p  is the node with the smallest key greater than  p.val .   Example 1: Input: root = [2,1,3] , p = 1 Output: 2 Explanation: 1's in-order successor node is 2. Note that both p and the return value is of TreeNode type. Example 2: Input: root = [5,3,6,2,4,null,null,1] , p = 6 Output: null Explanation: There is no in-order successor of the current node, so the answer is null .   Note: If the given node has no in-order successor in the tree, return  null . It's guaranteed that the values of the tree are unique. --- Related problems 701-insert-into-binary-search-tree ---

https://leetcode.com/problems/closest-binary-search-tree-value-ii/ https://github.com/openset/leetcode/tree/master/problems/closest-binary-search-tree-value-ii https://www.lintcode.com/problem/closest-binary-search-tree-value-ii/description Given a non-empty binary search tree and a target value, find  k  values in the BST that are closest to the target. Note: Given target value is a floating point. You may assume  k  is always valid, that is:  k  ≤ total nodes. You are guaranteed to have only one unique set of  k  values in the BST that are closest to the target. Example: Input: root = [4,2,5,1,3], target = 3.714286, and k = 2 4 / \ 2 5 / \ 1 3 Output: [4,3] Follow up: Assume that the BST is balanced, could you solve it in less than  O ( n ) runtime (where  n  = total nodes)? --- Related problems 270-closest-binary-search-tree-value --- ---

https://leetcode.com/problems/serialize-and-deserialize-bst/ Serialization is the process of converting a data structure or object into a sequence of bits so that it can be stored in a file or memory buffer, or transmitted across a network connection link to be reconstructed later in the same or another computer environment. Design an algorithm to serialize and deserialize a  binary search tree . There is no restriction on how your serialization/deserialization algorithm should work. You just need to ensure that a binary search tree can be serialized to a string and this string can be deserialized to the original tree structure. The encoded string should be as compact as possible. Note:  Do not use class member/global/static variables to store states. Your serialize and deserialize algorithms should be stateless. --- Related problems 297-serialize-and-deserialize-binary ---

https://leetcode.com/problems/unique-binary-search-trees/ Given  n , how many structurally unique  BST's  (binary search trees) that store values 1 ...  n ? Example: Input: 3 Output: 5 Explanation: Given n = 3, there are a total of 5 unique BST's: 1 3 3 2 1 \ / / / \ \ 3 2 1 1 3 2 / / \ \ 2 1 2 3 --- Related problems 95-unique-binary-search-trees-ii ---

https://leetcode.com/problems/kth-smallest-element-in-a-bst/ Given a binary search tree, write a function  kthSmallest  to find the  k th smallest element in it.   Example 1: Input: root = [3,1,4,null,2], k = 1 3 / \ 1 4 \   2 Output: 1 Example 2: Input: root = [5,3,6,2,4,null,null,1], k = 3 5 / \ 3 6 / \ 2 4 / 1 Output: 3 Follow up: What if the BST is modified (insert/delete operations) often and you need to find the kth smallest frequently? How would you optimize the kthSmallest routine?   Constraints: The number of elements of the BST is between  1  to  10^4 . You may assume  k  is always valid,  1 ≤ k ≤ BST's total elements . ---

https://leetcode.com/problems/unique-binary-search-trees-ii/ Given an integer  n , generate all structurally unique  BST's  (binary search trees) that store values 1 ...  n . Example: Input: 3 Output: [   [1,null,3,2],   [3,2,null,1],   [3,1,null,null,2],   [2,1,3],   [1,null,2,null,3] ] Explanation: The above output corresponds to the 5 unique BST's shown below: 1 3 3 2 1 \ / / / \ \ 3 2 1 1 3 2 / / \ \ 2 1 2 3 --- Related problems 96-unique-binary-search-trees ---

Given a Binary Search Tree and a target number, return true if there exist two elements in the BST such that their sum is equal to the given target. Example 1: Input: 5 / \ 3 6 / \ \ 2 4 7 Target = 9 Output: True   Example 2: Input: 5 / \ 3 6 / \ \ 2 4 7 Target = 28 Output: False ---

https://leetcode.com/problems/lowest-common-ancestor-of-a-binary-search-tree/ Given a binary search tree (BST), find the lowest common ancestor (LCA) of two given nodes in the BST. According to the  definition of LCA on Wikipedia : “The lowest common ancestor is defined between two nodes p and q as the lowest node in T that has both p and q as descendants (where we allow  a node to be a descendant of itself ).” Given binary search tree:  root = [6,2,8,0,4,7,9,null,null,3,5] Example 1: Input: root = [6,2,8,0,4,7,9,null,null,3,5], p = 2, q = 8 Output: 6 Explanation: The LCA of nodes 2 and 8 is 6 . Example 2: Input: root = [6,2,8,0,4,7,9,null,null,3,5], p = 2, q = 4 Output: 2 Explanation: The LCA of nodes 2 and 4 is 2 , since a node can be a descendant of itself according to the LCA definition. Note: All of the nodes' values will be unique. p and q are different and both values will exist in the BST. --- Clarifying quest...

https://leetcode.com/problems/convert-binary-search-tree-to-sorted-doubly-linked-list/ https://www.lintcode.com/problem/convert-binary-search-tree-to-sorted-doubly-linked-list/description Convert a BST to a sorted circular doubly-linked list in-place. Think of the left and right pointers as synonymous to the previous and next pointers in a doubly-linked list. Let's take the following BST as an example, it may help you understand the problem better: We want to transform this BST into a circular doubly linked list. Each node in a doubly linked list has a predecessor and successor. For a circular doubly linked list, the predecessor of the first element is the last element, and the successor of the last element is the first element. The figure below shows the circular doubly linked list for the BST above. The "head" symbol means the node it points to is the smallest element of the linked list. Specifically, we want to do the transformation in place. After...

https://leetcode.com/problems/construct-binary-search-tree-from-preorder-traversal/ Return the root node of a binary  search  tree that matches the given  preorder  traversal. (Recall that a binary search tree is a binary tree where for every  node , any descendant of  node.left  has a value  <   node.val , and any descendant of  node.right  has a value  >   node.val .  Also recall that a preorder traversal displays the value of the  node  first, then traverses  node.left , then traverses  node.right .) Example 1: Input: [8,5,1,7,10,12] Output: [8,5,10,1,7,null,12] Note:   1 <= preorder.length <= 100 The values of  preorder  are distinct. --- Intuition Build the tree recursively Left subtree has nodes less than root Right subtree has nodes less than upperBound Terminate recursion when index > Array length OR Array element > upper Bound --- ...

https://leetcode.com/problems/closest-binary-search-tree-value https://www.lintcode.com/problem/closest-binary-search-tree-value/description Given a non-empty binary search tree and a target value, find the value in the BST that is closest to the target. Note: Given target value is a floating point. You are guaranteed to have only one unique value in the BST that is closest to the target. Example: Input: root = [4,2,5,1,3], target = 3.714286 4 / \ 2 5 / \ 1 3 Output: 4 --- Intuition Find closest node tracking the min diff Pay attention to corner case - target >= Integer.MAX_VALUE Initialize the closest node to Double.MAX_VALUE --- Time - O(n) Space - O(h) - recursive call stack best case - O(log n) - balanced BST worst case - O(n) for one sided skewed BST --- Related problems 272-closest-binary-search-tree-value-ii