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: [-10,-3,0,5,9]
Output: 0
/ \
-3 9
/ /
-10 5
Input: head = [0]
Output: [0]
EDGE CASE
Input: head = []
Output: []
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.
If you are dealing with Binary Trees some common techniques you can employ to help you solve the problem:
Plan the solution with appropriate visualizations and pseudocode.
General Idea: This sorted linked list is also an inorder traversal. Find the mid of the array. Use it as root. Recursively call buildBST on the left nodes and right nodes and add them to the root.
1) Determine the size of the LL
2) Keep a global reference to a head variable that can change
3) Trigger Helper function with paramters 0 and size - 1 to indicate current scope
4) Return Helper function value
Helper
1) If the current L, R pointers are inverted, return
2) Calculate the midpoint of the L, R pointers
3) Recurse left (as an In-Order Traversal would) with params L and Mid - 1
4) Create a node with the current head node value and move the head pointer forward
5) Recurse right with params Mid + 1 and R
6) Attach left sub-tree from left recursion to current node
7) Attach right sub-tree from right recursion to current node
8) Return current node
⚠️ Common Mistakes
Implement the code to solve the algorithm.
class Solution:
def sortedListToBST(self, head: ListNode) -> TreeNode:
def helper(start, end):
# Basecase: If the current start and end pointers are inverted, return
if start > end:
return
global h
# Calculate the midpoint of the start and end pointers
mid = (start + end) // 2
# Recurse left (as an In-Order Traversal would) with params L and Mid - 1
left = helper(start, mid - 1)
# Create a node with the current head node value and move the head pointer forward
cur_node = TreeNode(h.val)
h = h.next
# Recurse right with params Mid + 1 and R
right = helper(mid + 1, end)
# Attach left sub-tree from left recursion to current node and Attach right sub-tree from right recursion to current node
cur_node.left, cur_node.right = left, right
# Return current node
return cur_node
def find_size(root):
ret = 0
while root:
ret += 1
root = root.next
return ret
# Determine the size of the LL
size = find_size(head)
# Keep a global reference to a head variable that can change
global h
h = head
# Trigger Helper function with paramters 0 and size - 1 to indicate current scope and Return Helper function value
return helper(0, size - 1)
class Solution {
ListNode head;
public TreeNode sortedListToBST(ListNode head) {
// Keep a global reference to a head variable that can change
this.head = head;
// Trigger Helper function with paramters 0 and size - 1 to indicate current scope and Return Helper function value
return buildBST(0, length(head) - 1);
}
TreeNode buildBST(int left, int right) {
// Basecase: If the current start and end pointers are inverted, return
if (left > right) return null;
// Calculate the midpoint of the start and end pointers
int mid = (left + right) / 2;
// Recurse left (as an In-Order Traversal would) with params L and Mid - 1
TreeNode leftNode = buildBST(left, mid - 1);
// Create a node with the current head node value and move the head pointer forward
TreeNode root = new TreeNode(head.val);
head = head.next;
// Recurse right with params Mid + 1 and R
// Attach left sub-tree from left recursion to current node and Attach right sub-tree from right recursion to current node
root.left = leftNode;
root.right = buildBST(mid + 1, right);
// Return current node
return root;
}
int length(ListNode head) {
int ans = 0;
while (head != null) {
head = head.next;
ans++;
}
return ans;
}
}
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 items in array