What is the worst-case time complexity of searching an element in a Binary Search Tree?O(1)O(log n)O(n)O(n log n)

The worst-case time complexity of searching an element in a Binary Search Tree (BST) is O(n).

Here's why:

1. A Binary Search Tree is a node-based binary tree data structure which has the following properties:

   • The left subtree of a node contains only nodes with keys lesser than the node’s key.
   • The right subtree of a node contains only nodes with keys greater than the node’s key.
   • The left and right subtree each must also be a binary search tree.

2. In the best-case scenario, the tree is perfectly balanced and the time complexity is O(log n). This is because with each comparison, we are able to eliminate half of the tree from consideration.

3. However, in the worst-case scenario, the tree can be skewed to the left or right. This means all the nodes are in a single line, like a linked list. In this case, we would have to traverse through all the nodes to find the element we are searching for.

4. Therefore, the worst-case time complexity of searching an element in a Binary Search Tree is O(n), where n is the number of nodes in the tree.