Validate Binary Search Tree Leetcode Problem 98 [Python Solution]

In this blog post, we’ll delve into the LeetCode problem titled Validate Binary Search Tree (Problem 98) under the “Trees” category.

We’ll explore how to determine whether a given binary tree is a valid binary search tree (BST).

If you’re new to binary search trees or looking for an efficient Python solution, you’re in the right place.

Let’s get started!

Question Link: Validate Binary Search Tree on LeetCode

Problem Overview

The task at hand is to determine if a given binary tree is a valid binary search tree (BST).

A valid BST follows these rules:

• 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.

Let’s look at an example for clarity.

Example 1:

Input:

root = [2, 1, 3]

Output:

true

This example demonstrates a valid binary search tree.

The root node contains the value 2, and its left child (1) has a smaller value, while the right child (3) has a larger value, adhering to the BST rules.

Understanding BST Constraints

Before we delve into the efficient Python solution, let’s understand the constraints of a binary search tree.

In a BST:

• The left subtree’s values are strictly less than the root node’s value.
• The right subtree’s values are strictly greater than the root node’s value.

Validate Binary Search Tree LeetCode Problem Solution

Now, let’s explore an efficient Python solution for this problem.

We will use a recursive approach to check each node’s validity.

1. Bruteforce Approach

A straightforward, but less efficient approach would involve comparing each node’s value to its ancestors and descendants.

This approach would require extensive comparisons, resulting in a time complexity of O(n^2).

Here’s a pseudocode representation of this approach:

function isBST(node, leftBoundary, rightBoundary):
    if node is null:
        return True
    if not (leftBoundary < node.val < rightBoundary):
        return False
    return isBST(node.left, leftBoundary, node.val) and isBST(node.right, node.val, rightBoundary)

2. An Efficient Approach with Pseudocode

To optimize the solution and avoid redundant comparisons, we can implement a more efficient recursive approach.

The key is to maintain updated boundaries as we traverse the tree.

function isValidBST(root, leftBoundary, rightBoundary):
    if root is null:
        return True
    if not (leftBoundary < root.val < rightBoundary):
        return False
    return isValidBST(root.left, leftBoundary, root.val) and isValidBST(root.right, root.val, rightBoundary)

This efficient approach ensures that we only perform one or two comparisons per node, resulting in a time complexity of O(n), where n is the number of nodes in the tree.

Python Code Solution

Here’s the Python code for the efficient solution:

def isValidBST(self, root: Optional[TreeNode]) -> bool:
    def valid(node, left, right):
        if not node:
            return True
        if not (left < node.val < right):
            return False
        return valid(node.left, left, node.val) and     

    valid(node.right, node.val, right)

    return valid(root, float("-inf"), float("inf"))

This Python code provides an elegant and efficient solution to the problem.

It leverages the recursive approach to ensure the validity of the binary search tree.

Time and Space Complexity

Let’s briefly discuss the time and space complexity of our solution.

• Time Complexity: The time complexity is O(n) because we visit each node once, performing a limited number of comparisons.
• Space Complexity: The space complexity is O(h), where h is the height of the binary tree.

In the worst case, when the tree is unbalanced, the space complexity can be O(n).

However, for balanced trees, it remains O(log n).

Reasoning Behind Our Approach

We’ve established an efficient approach for validating a binary search tree.

By maintaining boundaries while traversing the tree, we reduce the need for extensive comparisons, resulting in a time-efficient solution.

Related Interview Questions By Company:

• Two City Scheduling LeetCode
• Insert Interval LeetCode
• Unique Paths II LeetCode

Related Interview Questions By Difficulty:

• Binary Tree Postorder Traversal LeetCode
• Invert Binary Tree LeetCode
• Binary Tree Preorder Traversal LeetCode

Related Interview Questions By Category:

• Range Sum Query 2D Immutable LeetCode
• Simplify Path LeetCode
• Serialize And Deserialize Binary Tree LeetCode

Conclusion

In this blog post, we’ve explored the LeetCode problem Validate Binary Search Tree We’ve discussed the constraints of binary search trees and provided an efficient Python solution to determine whether a given tree is a valid binary search tree.

Our approach ensures a time complexity of O(n), making it a highly optimized solution.

If you found this guide helpful, please consider liking and subscribing.

Feel free to leave your questions, suggestions, or comments below.

Sharing this content can help others looking for solutions to similar problems.

Happy coding!

Note: For more details about this question, please refer to the LeetCode problem.