Is BST

The concept of "Is BST" refers to determining whether a given binary tree is a binary search tree (BST). A binary search tree is a binary tree in which the value of each node is greater than all the values in its left subtree and less than all the values in its right subtree.

Example: Let's consider an example to understand the "Is BST" concept better. We'll create a binary tree and check if it is a binary search tree.

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

# Function to check if a binary tree is a binary search tree
def isBST(root):
    def helper(node, lower=float('-inf'), upper=float('inf')):
        if not node:
            return True

        val = node.val
        if val <= lower or val >= upper:
            return False

        if not helper(node.right, val, upper):
            return False
        if not helper(node.left, lower, val):
            return False

        return True

    return helper(root)

# Create a binary tree
root = TreeNode(4)
root.left = TreeNode(2)
root.right = TreeNode(5)
root.left.left = TreeNode(1)
root.left.right = TreeNode(3)

# Check if the binary tree is a BST
is_bst = isBST(root)
print("Is BST?", is_bst)
# Output: Is BST? True

In this example, we define a function isBST that takes the root of a binary tree as input and returns a boolean value indicating whether the tree is a binary search tree.

The function uses a helper function helper that performs the recursive check for each node. It takes three arguments: the current node, the lower bound (the maximum value allowed in the left subtree), and the upper bound (the minimum value allowed in the right subtree).

Inside the helper function, it first checks if the current node exists. If not, it returns True as an empty tree is considered a valid BST.

It then checks if the value of the current node is within the valid range defined by the lower and upper bounds. If not, it returns False, indicating that the tree is not a valid BST.

Next, it recursively calls the helper function for the right subtree, passing the current node's value as the new lower bound. If this recursive call returns False, it means the right subtree is not a valid BST, and the function returns False.

Similarly, it recursively calls the helper function for the left subtree, passing the current node's value as the new upper bound. If this recursive call returns False, it means the left subtree is not a valid BST, and the function returns False.

If all the checks pass for the current node and its subtrees, the function returns True, indicating that the tree is a valid BST.

In the main code, we create a binary tree with the following structure:

We then call the isBST function with the root of the binary tree. The function recursively checks each node and its subtrees to determine if the tree satisfies the BST property. In this case, the binary tree is a valid BST, so the output is True.

The time complexity of this approach is O(n), where n is the number of nodes in the binary tree, as we visit each node exactly once. The space complexity is O(n) in the worst case, as the recursion stack can hold all the nodes in the tree for an unbalanced tree. However, for a balanced tree, the space complexity is O(log n) since the maximum depth of the recursion stack is the height of the tree.

Let's solve a question that involves determining whether a given binary tree is a valid BST. The problem we'll solve is "Validate Binary Search Tree".

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

# Function to check if a binary tree is a valid BST
def isValidBST(root):
    def helper(node, lower=float('-inf'), upper=float('inf')):
        if not node:
            return True

        val = node.val
        if val <= lower or val >= upper:
            return False

        if not helper(node.right, val, upper):
            return False
        if not helper(node.left, lower, val):
            return False

        return True

    return helper(root)

# Create a binary tree
root = TreeNode(2)
root.left = TreeNode(1)
root.right = TreeNode(3)

# Check if the binary tree is a valid BST
is_valid = isValidBST(root)
print("Is Valid BST?", is_valid)
# Output: Is Valid BST? True

In this example, we define a function isValidBST that takes the root of a binary tree as input and returns a boolean value indicating whether the tree is a valid BST.

Inside the helper function, it first checks if the current node exists. If not, it returns True as an empty tree is considered a valid BST.

It then checks if the value of the current node is within the valid range defined by the lower and upper bounds. If not, it returns False, indicating that the tree is not a valid BST.

If all the checks pass for the current node and its subtrees, the function returns True, indicating that the tree is a valid BST.

In the main code, we create a binary tree with the following structure:

    2
   / \
  1   3

We then call the isValidBST function with the root of the binary tree. The function recursively checks each node and its subtrees to determine if the tree satisfies the BST property. In this case, the binary tree is a valid BST, so the output is True.

Is BST

DIFFICULTY

COMPANY

Data Structures