We use cookies (including Google cookies) to personalize ads and analyze traffic. By continuing to use our site, you accept our Privacy Policy.

SimplyLeet
TagsCompaniesDisclaimersPrivacyTermsContactAbout Us

Validate Binary Search Tree

Number: 98

Difficulty: Medium

Paid? No

Companies: Bloomberg, Amazon, Google, Microsoft, Meta, Salesforce, Oracle, Yandex, Apple, IBM, SIG, TikTok, Adobe, Citadel, Nvidia, LinkedIn, Yahoo, Uber, ServiceNow, eBay, Paytm, Wix

Problem Description

Determine if a given binary tree is a valid Binary Search Tree (BST). A valid BST requires that for every node, nodes in its left subtree have values strictly less than the node’s value, and nodes in its right subtree have values strictly greater than the node’s value. These constraints must hold recursively for every subtree in the tree.

Key Insights

  • Every node must adhere to a range: all nodes in the left subtree should be less than the current node, and all nodes in the right subtree should be greater.
  • A recursive depth-first search approach works well by passing down the valid range (lower and upper bounds) for each node.
  • Using the limits (negative and positive infinity) simplifies handling edge cases at the tree root.
  • An in-order traversal would alternatively yield a sorted order for node values, but updating ranges directly is more intuitive for recursive implementation.

Space and Time Complexity

Time Complexity: O(N), where N is the number of nodes, as each node is visited once. Space Complexity: O(H), where H is the height of the tree, due to the recursion stack.

Solution

We use a recursive approach to validate the BST property. We maintain two variables, low and high, representing the valid range for the current node’s value. For the left child, the valid range becomes (low, node.val) and for the right child, it becomes (node.val, high). By checking if each node’s value falls within its respective range, we can ensure that the tree satisfies the BST properties.

Code Solutions

# Definition for a binary tree node.
class TreeNode:
    def __init__(self, val=0, left=None, right=None):
        self.val = val      # Node's value
        self.left = left    # Left child
        self.right = right  # Right child

class Solution:
    def isValidBST(self, root: TreeNode) -> bool:
        # Helper function to recursively validate nodes
        def validate(node, low, high):
            if not node:
                return True  # An empty node/subtree is valid
            # If current node's value is out of the allowed range, return False
            if not (low < node.val < high):
                return False
            # Recursively check the left subtree and right subtree
            return validate(node.left, low, node.val) and validate(node.right, node.val, high)
        
        return validate(root, float("-inf"), float("inf"))
← Back to All Questions