Binary Search Tree (BST)


A Binary Search Tree (BST) is a binary tree data structure in which the values of nodes in the left subtree are less than or equal to the value of the root node, and the values of nodes in the right subtree are greater than the value of the root node. This ordering property allows for efficient search, insertion, and deletion operations.

Example: Let's create a Binary Search Tree and perform some operations on it.

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

# Binary Search Tree class definition
class BinarySearchTree:
    def __init__(self):
        self.root = None

    # Insert a node into the BST
    def insert(self, value):
        if self.root is None:
            self.root = Node(value)
        else:
            self._insert_helper(self.root, value)

    # Helper function to recursively insert a node
    def _insert_helper(self, node, value):
        if value < node.value:
            if node.left is None:
                node.left = Node(value)
            else:
                self._insert_helper(node.left, value)
        else:
            if node.right is None:
                node.right = Node(value)
            else:
                self._insert_helper(node.right, value)

    # Search for a value in the BST
    def search(self, value):
        return self._search_helper(self.root, value)

    # Helper function to recursively search for a value
    def _search_helper(self, node, value):
        if node is None or node.value == value:
            return node
        if value < node.value:
            return self._search_helper(node.left, value)
        else:
            return self._search_helper(node.right, value)

# Create an instance of Binary Search Tree
bst = BinarySearchTree()

# Insert nodes into BST
bst.insert(50)
bst.insert(30)
bst.insert(70)
bst.insert(20)
bst.insert(40)
bst.insert(60)
bst.insert(80)

# Search for a value
result = bst.search(40)
print(result.value)
# Output: 40

In this example, we define a Node class that represents a node in the Binary Search Tree. Each node has a value, left child, and right child.

We also define a BinarySearchTree class to perform Binary Search Tree operations. The class has methods for inserting a new node and searching for a value in the BST.

The insert method inserts a new node into the BST based on the ordering property. If the BST is empty, the new node becomes the root. Otherwise, the _insert_helper function is called recursively to find the correct position to insert the new node.

The search method searches for a value in the BST by calling the _search_helper function recursively. If the value is found, the corresponding node is returned; otherwise, None is returned.

Let's solve a question using the concept of Binary Search Tree. The question is "Validate Binary Search Tree," which requires determining whether a given binary tree is a valid BST.


class Node:
    def __init__(self, value):
        self.value = value
        self.left = None
        self.right = None

class Solution:
    def is_valid_bst(self, root):
        def is_valid_bst_helper(node, lower=float('-inf'), upper=float('inf')):
            if node is None:
                return True
            if node.value <= lower or node.value >= upper:
                return False
            return (is_valid_bst_helper(node.left, lower, node.value) and
                    is_valid_bst_helper(node.right, node.value, upper))

        return is_valid_bst_helper(root)

# Create an instance of Solution
solution = Solution()

# Create a binary tree
root = Node(5)
root.left = Node(3)
root.right = Node(7)
root.left.left = Node(2)
root.left.right = Node(4)
root.right.left = Node(6)
root.right.right = Node(8)

# Check if the binary tree is a valid BST
print(solution.is_valid_bst(root))
# Output: True

In this solution, we define a Node class to represent a node in the binary tree. We also define a Solution class that contains the is_valid_bst method to check if a given binary tree is a valid BST.

The is_valid_bst method uses a helper function is_valid_bst_helper to recursively check the validity of each node in the binary tree. It takes three parameters: the current node, the lower bound (minimum value allowed), and the upper bound (maximum value allowed) for the current node's value. It performs the following checks:

  • If the current node is None, it is a valid BST (base case).
  • If the current node's value is not within the lower and upper bounds, it is not a valid BST.
  • Recursively check the left subtree with the updated upper bound as the current node's value and the right subtree with the updated lower bound as the current node's value.

The time complexity of the solution is O(n), where n is the number of nodes in the binary tree, as we visit each node once. The space complexity is O(n) in the worst case, as the recursion stack may grow up to the number of nodes in the tree.

Next Post Previous Post