Binary Search Tree Recursive

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.

Recursive approach is commonly used to implement operations on a BST, as it takes advantage of the recursive nature of the tree structure.

Example: Let's create a Binary Search Tree using recursive approach 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):
        self.root = self._insert_helper(self.root, value)

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

    # 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 using a recursive approach. If the current node is None, a new node with the given value is created. Otherwise, the method recursively calls itself on the left or right child of the current node based on the comparison of values.

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.

Competitive Question Solution: Let's solve a medium-level competitive question from LeetCode using the concept of Binary Search Tree and the recursive approach. The question is "Kth Smallest Element in a BST," which requires finding the Kth smallest element in a BST.

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

class Solution:
    def kth_smallest(self, root, k):
        def inorder_traversal(node):
            nonlocal k, result

            if node is None:
                return

            inorder_traversal(node.left)

            k -= 1
            if k == 0:
                result = node.value
                return

            inorder_traversal(node.right)

        result = None
        inorder_traversal(root)

        return result

# 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)

# Find the 3rd smallest element
result = solution.kth_smallest(root, 3)
print(result)
# Output: 4

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 kth_smallest method to find the Kth smallest element in a BST.

The kth_smallest method performs an inorder traversal of the BST using a recursive helper function inorder_traversal. The inorder_traversal function visits the nodes in the BST in ascending order. It updates the k value and checks if k is equal to 0 at each node. If k becomes 0, it means we have found the Kth smallest element, and the result is updated accordingly.