Understand what the interviewer is asking for by using test cases and questions about the problem.
- Established a set (2-3) of test cases to verify their own solution later.
- Established a set (1-2) of edge cases to verify their solution handles complexities.
- Have fully understood the problem and have no clarifying questions.
- Have you verified any Time/Space Constraints for this problem?
HAPPY CASE
Input: [1, 2, 3, 4, 5]
Output:
3
/ \
2 4
/ \
1 5
Input: [1, 2, 3, 4, 5, 6, 7, 8]
Output:
4
/ \
2 6
/ \ / \
1 3 5 7
\
8
(Note the subtrees differ in height by 1, but not more than 1)
EDGE CASE (No elements)
Input: []
Output: None
Match what this problem looks like to known categories of problems, e.g. Linked List or Dynamic Programming, and strategies or patterns in those categories.
For trees, some things we should consider are:
Plan the solution with appropriate visualizations and pseudocode.
General Idea: Use fact that the array is sorted and the idea of searching the mid point with each loop during binary search. We recursively get the mid point of the array as root and recursively call for left child with first half of array and right child with second half of array. Because the mid point of each recursive array is the point where we can branch off smaller elements on left and larger elements on right.
1) Basecase: Check for an empty input list. If it is empty, return None (an empty BST)
2) Recursively:
a) Get the index of the root node from the list (this will be the element at the center of the input list)
b) Build the left and right subtrees of the tree by recursively calling the function on each remaining half of the input list
3) Return the root of the tree
âš ď¸Ź Common Mistakes
Implement the code to solve the algorithm.
class Solution {
int[] nums;
public TreeNode helper(int left, int right) {
if (left > right) return null;
// always choose left middle node as a root
int p = (left + right) / 2;
// preorder traversal: node -> left -> right
TreeNode root = new TreeNode(nums[p]);
root.left = helper(left, p - 1);
root.right = helper(p + 1, right);
return root;
}
public TreeNode sortedArrayToBST(int[] nums) {
this.nums = nums;
return helper(0, nums.length - 1);
}
}
class Solution:
def sortedArrayToBST(self, nums: List[int]) -> Optional[TreeNode]:
# Basecase: Check for an empty input list. If it is empty, return None (an empty BST)
if not nums:
return None
# Recursively: Get the index of the root node from the list (this will be the element at the center of the input list)
mid = len(nums) // 2
root = TreeNode(nums[mid])
# Recursively: Build the left and right subtrees of the tree by recursively calling the function on each remaining half of the input list
root.left = self.sortedArrayToBST(nums[:mid])
root.right = self.sortedArrayToBST(nums[mid + 1:])
# Return the root of the tree
return root
Review the code by running specific example(s) and recording values (watchlist) of your code's variables along the way.
Evaluate the performance of your algorithm and state any strong/weak or future potential work.
Assume N
represents the number of nodes in the tree.