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

SimplyLeet
TagsDisclaimersPrivacyTermsContactAbout Us

Validate Binary Search Tree

Difficulty: Medium

Problem Description

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.

Key Insights

  • A binary search tree (BST) must maintain the ordering property for each node.
  • The in-order traversal of a BST results in a sorted sequence of values.
  • Recursion or iterative approaches can be used to validate the BST.
  • We can keep track of the valid range for each node as we traverse the tree.

Space and Time Complexity

Time Complexity: O(n), where n is the number of nodes in the tree, as we may need to visit each node once. Space Complexity: O(h), where h is the height of the tree, due to the recursion stack in a depth-first search approach.

Solution

To determine if a binary tree is a valid binary search tree, we can use a recursive approach where we check each node to ensure it falls within a valid range defined by its ancestors. For each node, we will:

  1. Check if the node's value is greater than the lower bound and less than the upper bound.
  2. Recursively validate the left and right subtrees, updating the bounds accordingly.

The data structure used is a binary tree, and the algorithmic approach is depth-first search (DFS).

Code Solutions

def isValidBST(root, lower=float('-inf'), upper=float('inf')):
    if not root:
        return True
    val = root.val
    if val <= lower or val >= upper:
        return False
    return (isValidBST(root.left, lower, val) and 
            isValidBST(root.right, val, upper))
← Back to All Questions