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?
O(n)
time and O(1)
space complexity without the recursive stack.HAPPY CASE
Input: root = [2,1,3]
Output: true
Input: root = [5,1,4,null,null,3,6]
Output: false
Explanation: The root node's value is 5 but its right child's value is 4.
EDGE CASE
Input: root = [1]
Output: true
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: Recursive pre-order traversal to help valid each node. A valid node is between the maximum value and minimum value determined by parent nodes.
1) Create a helper function that processes tree via pre-order traversal while retaining the maximum value and minimum value of node as determined by parent nodes.
a) Base Case: Check if the root is None. If it is, return true. We made it to the leaf of a tree and every node along the path is valid.
b) Check if the node is within minimum and maximum range. If it is not, return false.
b) Call helper on left child, when going left, update the maximum value of child node is less than parent node
c) Call helper on right child, when going right, update the minimum value of child node is greater than parent node
2) Call helper function on root and set minimum value of node to be negative infinite and maximum value of node to be positive infinite
⚠️ Common Mistakes
Implement the code to solve the algorithm.
# Definition for a binary tree node.
# class TreeNode:
# def __init__(self, val=0, left=None, right=None):
# self.val = val
# self.left = left
# self.right = right
class Solution:
def isValidBST(self, root: Optional[TreeNode]) -> bool:
# Create a helper function that processes tree via pre-order traversal while retaining the maximum value and minimum value of node as determined by parent nodes.
def helper(node: Optional[TreeNode], minimumValueOfNode: int, maximumValueOfNode: int) -> bool:
# Check if the node is None. If it is, return true. We made it to the leaf of a tree and every node along the path is valid.
if not node:
return True
# Check if the node is within minimum and maximum range. If it is not, return false.
if node.val <= minimumValueOfNode or node.val >= maximumValueOfNode:
return False
# Call helper on left child, when going left, update the maximum value of child node is less than parent node
# Call helper on right child, when going right, update the minimum value of child node is greater than parent node
return helper(node.left, minimumValueOfNode, node.val) and helper(node.right, node.val, maximumValueOfNode)
# Call helper function on root and set minimum value of node to be negative infinite and maximum value of node to be positive infinite
return helper(root, -math.inf, math.inf)
public class Solution {
public boolean isValidBST(TreeNode root) {
// Call helper function on root and set minimum value of node to be negative infinite and maximum value of node to be positive infinite
return isValidBST(root, Long.MIN_VALUE, Long.MAX_VALUE);
}
// Create a helper function that processes tree via pre-order traversal while retaining the maximum value and minimum value of node as determined by parent nodes.
public boolean isValidBST(TreeNode root, long minVal, long maxVal) {
// Check if the node is None. If it is, return true. We made it to the leaf of a tree and every node along the path is valid.
if (root == null) return true;
// Check if the node is within minimum and maximum range. If it is not, return false.
if (root.val >= maxVal || root.val <= minVal) return false;
// Call helper on left child, when going left, update the maximum value of child node is less than parent node
// Call helper on right child, when going right, update the minimum value of child node is greater than parent node
return isValidBST(root.left, minVal, root.val) && isValidBST(root.right, root.val, maxVal);
}
}
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 binary search tree.