# Search Operation in BST

### Searching in BST

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

Start at the root node of the BST.

Compare the search key with the key of the root node.

If the search key matches the root node's key, the search is successful. Return the root node or any relevant information.

If the search key is less than the root node's key, move to the left child of the root node.

If the search key is greater than the root node's key, move to the right child of the root node.

Repeat steps 2 to 5 until one of the following conditions is met:

The current node is None, indicating that the search key is not present in the BST. Return a suitable indication, such as None or a boolean value (False).

The search key is found in a node. Return the node or any relevant information.

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:

Start at the root node, which is 20.

Compare the key 7 with the current node's key, which is 20.

Since 7 is less than 20, move to the left child of the current node, which is 5.

Compare the key 7 with the current node's key, which is 5.

Since 7 is greater than 5, move to the right child of the current node, which is 15.

Compare the key 7 with the current node's key, which is 15.

Since 7 is less than 15, move to the left child of the current node, which is 9.

Compare the key 7 with the current node's key, which is 9.

Since 7 is less than 9, move to the left child of the current node, which is 7.

Compare the key 7 with the current node's key, which is 7.

The key 7 is found in the BST.

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.")