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: root = [4,2,7,1,3], val = 5
Output: [4,2,7,1,3,5]
Input: root = [40,20,60,10,30,50,70], val = 25
Output: [40,20,60,10,30,50,70,null,null,25]
EDGE CASE
Input: root = [4,2,7,1,3,null,null,null,null,null,null], val = 5
Output: [4,2,7,1,3,5]
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: Recursively traverse binary search trees for the correct position for the current value, by going left if a larger value is seen or going right if a smaller value is seen.
1) Base Case: Check if the tree is empty. If it is, return a new TreeNode with node value of val
2) Recursively traverse the tree in pre-order fashion
a) Compare the input value with the node values
i) If input value > node.val: traverse the left subtree
ii) Else traverse the right subtree
3) Return the root of the tree
⚠️ Common Mistakes
Implement the code to solve the algorithm.
class Solution:
def insertIntoBST(self, root: Optional[TreeNode], val: int) -> Optional[TreeNode]:
# Check if the tree is empty. If it is, return a new TreeNode with node value of val
if not root:
return TreeNode(val)
# Recursively traverse the tree in pre-order fashion
if root.val > val:
# If node.val > input value: traverse the left subtree
root.left = self.insertIntoBST(root.left, val)
else:
# Else traverse the right subtree
root.right = self.insertIntoBST(root.right, val)
# Return the root of the tree
return root
class Solution {
public TreeNode insertIntoBST(TreeNode root, int val) {
// Check if the tree is empty. If it is, return a new TreeNode with node value of val
if(root==null)
return new TreeNode(val);
// Recursively traverse the tree in pre-order fashion
// If node.val > input value: traverse the left subtree
if(root.val>val)
root.left = insertIntoBST(root.left,val);
// Else traverse the right subtree
else
root.right = insertIntoBST(root.right,val);
// 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 H
represents the height of the binary search tree