98. Validate Binary Search Tree#

Difficulty: Medium

Link to Problem: To see the Validate Binary Search Tree problem on LeetCode, click here!

Given the root of a binary tree, determine if it is a valid binary search tree (BST).

A valid BST is defined as follows:

  • The left subtree of a node contains only nodes with keys less than the node’s key.

  • The right subtree of a node contains only nodes with keys greater than the node’s key.

  • Both the left and right subtrees must also be binary search trees.

Constraints:

  • The number of nodes in the tree is in the range \([1, 10^4]\).

  • \(-2^{31}\) <= Node.val <= \(2^{31} - 1\)

Solution:#

Here’s a Python function to solve this problem:

class TreeNode:
    def __init__(self, val=0, left=None, right=None):
        self.val = val
        self.left = left
        self.right = right

def is_valid_BST(root):
    def is_valid(node, min_val, max_val):
        # Base case: If the node is None, it's a valid BST.
        if node is None:
            return True
        
        # Check if the current node's value is within the valid range.
        if not (min_val < node.val < max_val):
            return False
        
        # Recursively check the left and right subtrees with updated ranges.
        return (is_valid(node.left, min_val, node.val) and
                is_valid(node.right, node.val, max_val))
    
    # Call the helper function starting with a wide range for root node.
    return is_valid(root, float('-inf'), float('inf'))

Explanation:#

  • It defines a TreeNode class to represent nodes in the binary tree.

  • The is_valid_BST function takes the root node of the binary tree as input and returns True if the tree is a valid BST, and False otherwise.

  • Inside the is_valid_BST function, there is a helper function called is_valid that performs the actual validation using a recursive approach.

  • The is_valid function checks each node in the tree to ensure that it satisfies the properties of a BST:

    • The value of the current node must be within a valid range defined by min_val and max_val.

    • The left subtree of the current node should contain values less than the current node’s value.

    • The right subtree of the current node should contain values greater than the current node’s value.

  • If any of these conditions are violated, the function returns False, indicating that the tree is not a valid BST.

  • If all nodes satisfy these conditions, the function returns True, indicating that the tree is a valid BST.

  • The code calls the is_valid function with the root node and initial range values of negative infinity to positive infinity to start the validation.

  • The time complexity of the code is O(N), where N is the number of nodes in the tree, as it traverses each node once.

  • The space complexity depends on the height of the tree. In the average case for a balanced BST, the space complexity is O(log N), but in the worst case (skewed tree), it can be O(N) due to the recursive call stack.

In summary, this code checks whether a given binary tree is a valid BST by recursively validating each node’s value and its left and right subtrees while maintaining valid value ranges. If all nodes satisfy the BST properties, the tree is considered a valid BST.

Test cases#

# Example 1: 

# Example usage:
# Create the tree for the first example: [2, 1, 3]
root1 = TreeNode(2)
root1.left = TreeNode(1)
root1.right = TreeNode(3)
print(is_valid_BST(root1))

True

# Example 2:

# Create the tree for the second example: [5, 1, 4, None, None, 3, 6]
root2 = TreeNode(5)
root2.left = TreeNode(1)
root2.right = TreeNode(4)
root2.right.left = TreeNode(3)
root2.right.right = TreeNode(6)
print(is_valid_BST(root2))

False

Time and Space Complexity Analysis#

Let’s analyze the time and space complexity of the is_valid_BST function:

Time Complexity:

  • The time complexity of the function primarily depends on the number of nodes in the binary tree.

  • In the worst case, we may have to visit every node in the tree once to validate whether it’s part of a valid BST.

  • Since we are performing a depth-first search (DFS) traversal of the tree, the time complexity is O(N), where N is the number of nodes in the tree.

Space Complexity:

  • The space complexity is determined by the space used by the recursive call stack during the DFS traversal.

  • In the worst case, if the tree is completely unbalanced (a skewed tree), the maximum depth of the call stack would be equal to the height of the tree.

  • In a balanced BST, the height is approximately log2(N), where N is the number of nodes.

  • Therefore, the space complexity of the call stack is O(log N) for a balanced BST.

  • In the worst case (skewed tree), the space complexity can be O(N) as the height of the tree can be equal to N.

Overall:

  • Time Complexity: O(N)

  • Space Complexity: O(log N) on average for a balanced BST, and O(N) in the worst case for a skewed tree.

The space complexity is typically dominated by the recursive call stack, and it varies depending on the shape of the binary tree. In practice, for balanced binary trees, the space complexity is often close to O(log N), which is quite efficient.

Challenging Exercises:#

  1. Complex Constraints: Modify the problem to have more complex constraints on the tree. For example, consider a binary tree with constraints like “The left subtree of a node contains only nodes with keys less than or equal to the node’s key,” and “The right subtree of a node contains only nodes with keys greater than or equal to the node’s key.” How would you adapt the code to handle these constraints?

  2. Handling Duplicates: Modify the code to handle binary search trees that allow duplicate values. In a standard BST, each value is unique, but in this case, multiple nodes can have the same value. The tree should still be considered valid if it follows the BST property.