Given the root
of a binary tree, determine if it is a valid binary search tree (BST). A valid BST is defined as follows:
For example, consider the following binary tree:
5
/ \
1 4
/ \
3 6
Is this a valid BST? The answer is false, because the node with value 4 is the right child of the node with value 5, but 4 < 5. The node with value 3 is the left child of the node with value 4, but 3 < 4. The node with value 6 is the right child of the node with value 4, and 6 > 4. Also, the subtrees rooted at 1, 3 and 6 are valid BSTs.
Another example:
2
/ \
1 3
This is a valid BST. The node with value 1 is the left child of the node with value 2, and 1 < 2. The node with value 3 is the right child of the node with value 2, and 3 > 2. Also, the subtrees rooted at 1 and 3 are valid BSTs.
Write an efficient algorithm to determine if a given binary tree is a valid BST.
When you get asked this question in a real-life environment, it will often be ambiguous (especially at FAANG). Make sure to ask these questions in that case:
To check if a tree is a valid Binary Search Tree (BST) using a brute force method, we essentially want to confirm that every node follows the BST property: smaller values on the left and larger values on the right. This involves exhaustively examining each node in relation to all other nodes within its potential range.
Here's how the algorithm would work step-by-step:
def is_valid_bst_brute_force(root):
def is_valid_subtree(node, less_than_value, greater_than_value):
if node is None:
return True
# Check if the current node violates the BST property
if not (less_than_value is None or node.val < less_than_value) or \
not (greater_than_value is None or node.val > greater_than_value):
return False
# Recursively check the left and right subtrees
# Ensure the left subtree is less than the current node
if not is_valid_subtree(node.left, node.val, greater_than_value):
return False
# Ensure the right subtree is greater than the current node
if not is_valid_subtree(node.right, less_than_value, node.val):
return False
return True
# Begin the validation from the root node
return is_valid_subtree(root, None, None)
To check if a tree is a valid Binary Search Tree, we use the properties that each node's value must fall within a specific range. This approach uses the tree's structure to efficiently confirm that these properties hold true for all nodes, without explicitly checking every possible relationship.
Here's how the algorithm would work step-by-step:
def is_valid_bst(root):
def validate_node(node, minimum_value, maximum_value):
if not node:
return True
# Check current node's value is within bounds
if not (minimum_value < node.val < maximum_value):
return False
# Ensure left subtree is a valid BST
if not validate_node(node.left, minimum_value, node.val):
return False
# Ensure right subtree is a valid BST
if not validate_node(node.right, node.val, maximum_value):
return False
return True
# Start validation with unbounded min/max values
return validate_node(root, float('-inf'), float('inf'))
Case | How to Handle |
---|---|
Null root node | An empty tree is considered a valid BST, so return true. |
Single node tree | A tree with only a root node is a valid BST, so return true. |
Tree with duplicate values (adjacent to each other) | The valid BST definition requires strict inequality; the solution should check that the left subtree is strictly less than the node and the right subtree is strictly greater than the node. |
Tree with duplicate values (non-adjacent, violating BST property) | The recursive calls will eventually find the violation where a node in the left or right subtree has an invalid value. |
Tree with negative values | The comparison should work correctly with negative values as integers are comparable in a standard way. |
Very large tree (potential stack overflow with recursion) | Iterative solutions using a stack may be preferred to avoid stack overflow errors for very large trees, limiting recursion depth. |
Tree with Integer.MAX_VALUE and Integer.MIN_VALUE | Ensure initial min/max bounds are set such that comparisons with these extreme values work correctly to avoid overflow problems. |
Skewed Tree (all nodes on one side) | The solution should still correctly validate a skewed tree because it checks all nodes against the allowed min/max range within the entire tree, though performance might degrade. |