Searching for an Element in a Binary Search Tree

Understanding Binary Search Tree Search

A Binary Search Tree (BST) is a binary tree with the following properties:

• The left subtree of a node contains only nodes with values less than the node's value.
• The right subtree of a node contains only nodes with values greater than the node's value.
• No duplicate nodes are allowed.

These properties enable efficient searching in O(log n) time in balanced trees. In a BST, to search for an element, we start at the root and compare the value to be searched with the current node's value. Depending on the comparison, we move to either the left or right subtree.

Consider the following example of a Binary Search Tree:

                8
               / \
              3   10
             / \    \
            1   6    14
               /  \   /
              4   7  13
            

Now, let's search for the element 7 in the tree using both recursive and iterative methods.

Recursive Approach

The recursive approach for searching in a BST works by comparing the target value with the current node's value. If the target is smaller, the search continues in the left subtree. If the target is larger, the search moves to the right subtree.

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

# Recursive Search Function
def search_recursive(root, target):
    if root is None:
        return False
    if root.value == target:
        return True
    # Search left or right subtree
    elif target < root.value:
        return search_recursive(root.left, target)
    else:
        return search_recursive(root.right, target)

# Example Usage
root = TreeNode(8)
root.left = TreeNode(3)
root.right = TreeNode(10)
root.left.left = TreeNode(1)
root.left.right = TreeNode(6)
root.right.right = TreeNode(14)
root.left.right.left = TreeNode(4)
root.left.right.right = TreeNode(7)
root.right.right.left = TreeNode(13)

target = 7
if search_recursive(root, target):
    print(f"Element {target} found in the binary search tree.")
else:
    print(f"Element {target} not found in the binary search tree.")
            

Iterative Approach

The iterative approach works similarly to the recursive approach but uses a loop to traverse the tree. We use a stack or a queue to maintain the nodes to be visited.

# Iterative Search Function
def search_iterative(root, target):
    while root:
        if root.value == target:
            return True
        elif target < root.value:
            root = root.left
        else:
            root = root.right
    return False

# Example Usage
target = 7
if search_iterative(root, target):
    print(f"Element {target} found in the binary search tree.")
else:
    print(f"Element {target} not found in the binary search tree.")