How to search for an element in a binary search tree

A binary search tree (BST) is a type of binary tree data structure characterized by the following attributes:

Binary tree structure: Every node within a binary search tree can have a maximum of two child nodes, the left child and the right child.
Ordered property: Each node in the tree ensures that values in its left subtree are less than the node’s value and values in its right subtree are greater. This inherent order enhances the efficiency of search, insertion, and deletion operations.

The structured characteristic guarantees an efficient search for a specific value in the tree by employing a process of elimination. If the target value is lower than the current node’s value, the search progresses to the left subtree; conversely, if it is greater, the search proceeds to the right subtree. Let’s suppose we have the following binary search tree:

Binary search trees find frequent applications in searching, inserting, and deleting elements while preserving their ordered arrangement. In a well-balanced binary search tree, the average time complexity for these operations is $O(log (n))$ , where $n$ represents the number of nodes. Nevertheless, in the worst-case scenario, where the tree is skewed and resembles a linked list, the time complexity can escalate to $O(n)$ .

Searching for an element in the BST

To locate an element in a binary search tree (BST), the process entails navigating the tree strategically, capitalizing on its organized arrangement. The following is a systematic guide on how to search for an element in a BST:

Step 1: Start the search at the root of the tree.

Step 2: Compare the target element with the value of the current node.

Step 3: Navigate left or right:

If the target element matches the value of the current node, the element has been located, and the search is deemed successful.
In case the target element is smaller than the current node’s value, navigate to the left subtree since, in a BST, all elements within the left subtree are less than the current node’s value.
In case the target element exceeds the current node’s value, proceed to the right subtree, as all elements in the right subtree are greater than the current node’s value in a BST.

Step 4: Continue with steps 2 and 3 iteratively until we either locate the element or reach a null (empty) node.

Let's say we need to search for a node having 5 as the key. Following is a demonstration of how it works:

def search(node, target):
    # Check to see if node is null and target element not found
    if node is None:
        return("Node not found", None)
    # Check if the key of the node is equal to the target
    if target == node.key:
        return("Node found:", node) 
    # If key of the target element is less than the key of the 
    # current node we travserse the left subtree
    elif target < node.key:
        return search(node.left, target)
# If key of the target element is greater than the key of the 
# current node we travserse the right subtree
    else:
        return search(node.right, target)
# Defining the data structure for the BST
class node:
    def __init__(self, key):
        self.key = key
        self.left = None
        self.right = None
# Populating the tree
BST= node(10)
BST.right=node (12)
BST.left=node (8)
BST.right.right = node (15)
BST.right.left = node (11)
BST.left.right = node (9)
BST.left.left = node (5)
# Printing the output
print(search(BST, 5))

Explanation

The explanation of the code is given below:

Line 1: We define a recursive function named search with two parameters: node, representing the current node under examination, and target, which is the value being sought.
Lines 2–4: We check if the current node is null and return None signifying that the element is absent in the BST.
Lines 6–8: In the event that the target element matches the value of the current node, the element has been located within the BST, and we proceed to return the current node.
Lines 11–14: If the target element is smaller than the value of the current node, we initiate a recursive call to search on the left subtree, as the target is expected to be situated in the left subtree of a BST.
Lines 16–19: In case the target element surpasses the value of the current node, we invoke a recursive call to search on the right subtree, as the target is anticipated to be situated in the right subtree of a BST.
Lines 21–26: We define the node class for use as the data structure for our BST.
Lines 28–35: We create a sample binary search tree to test out the search function.
Lines 37–38: These lines are test cases for our search function. Try them out and see how the output differs.

Note: The inherent recursion in this function enables it to traverse the BST until it either locates the target element or establishes that the element is absent in the tree. Read Recursion in Python Tutorial if not familiar to recursion.

Conclusion

In this Answer, we explored the fundamentals of binary search trees (BSTs), focusing on their search operations and Python implementation. Understanding BSTs is crucial for efficient data storage and retrieval, offering benefits in programming and data management. Due to their ability to expedite search operations and enhance application performance, BSTs are frequently used in algorithms and data structures.

If you're interested in learning about binary search trees more, don't miss out on exploring the following Answers.

Free AI Mock Interviews

Coding Interview

Coding PatternsFree Interview

Gain insights and practical experience with coding patterns through targeted MCQs and coding problems, designed to match and challenge your expertise level.

System Design

You TubeFree Interview

Learn to design a video streaming platform like YouTube by tackling functional and non-functional requirements, core components, and high-level to detailed design challenges.

Free Resources

How to search for an element in a binary search tree

Searching for an element in the BST

Code implementation

Explanation

Conclusion