Search Operation in BST

Searching in BST

Searching in a Binary Search Tree (BST) involves the following process:

During the search process, the BST property guides us in choosing the appropriate subtree to explore based on the comparison of keys. By traversing the BST from the root to the desired node, we efficiently locate the node with the search key or determine its absence in the tree.

Example

Searching in a Binary Search Tree (BST) involves the following process:

Therefore, the search steps to find 7 in the given BST are: 20 -> 5 -> 15 -> 9 -> 7.

Code Snippet

Here's an example of Python code that demonstrates the search algorithm for finding a key in a Binary Search Tree (BST):

class Node:

    def __init__(self, key):

        self.key = key

        self.left = None

        self.right = None

def search(root, key):

    if root is None or root.key == key:

        return root

    if key < root.key:

        return search(root.left, key)

    else:

        return search(root.right, key)


# Create a BST

root = Node(20)

root.left = Node(5)

root.right = Node(30)

root.left.left = Node(1)

root.left.right = Node(15)

root.left.right.left = Node(9)

root.left.right.left.left = Node(7)

root.left.right.left.right = Node(12)

root.right.left = Node(25)

root.right.right = Node(40)


# Search for key 7 in the BST

key = 7

result = search(root, key)


# Check if the key was found

if result is not None:

    print(f"Key {key} found in the BST.")

else:

    print(f"Key {key} not found in the BST.")