Wednesday, January 15, 2025
HomeTechSearching in Binary Search Tree (BST)
Tech

Searching in Binary Search Tree (BST)

Jason Smith
By Jason Smith
0
1
Searching in Binary Search Tree (BST)

Searching in a Binary Search Tree (BST) is an efficient process due to the properties of the BST. A BST is a binary tree where:

  1. The value of each node in the left subtree is less than the value of the root.
  2. The value of each node in the right subtree is greater than the value of the root.
  3. These properties apply recursively to all subtrees.

Algorithm for Searching in a BST

To search for a key in a BST, the following steps are used:

  1. Start at the root of the tree.
  2. Compare the key to be searched with the value of the current node:
    • If the key matches the current node value, the search is successful.
    • If the key is less than the current node value, move to the left subtree.
    • If the key is greater than the current node value, move to the right subtree.
  3. Repeat the process until:
    • The key is found, or
    • A NULL (empty subtree) is encountered, meaning the key is not in the tree.
See also  Insertion of Sort Algorithm

Recursive Implementation

python
class Node:
def __init__(self, key):
self.key = key
self.left = None
self.right = None

def search_bst(root, key):
# Base case: root is null or the key is present at root
if root is None or root.key == key:
return root

# Key is smaller than root's key -> search in the left subtree
if key < root.key:
return search_bst(root.left, key)

# Key is larger than root's key -> search in the right subtree
return search_bst(root.right, key)

# Example usage:
root = Node(10)
root.left = Node(5)
root.right = Node(20)
root.left.left = Node(3)
root.left.right = Node(7)

key_to_search = 7
result = search_bst(root, key_to_search)

if result:
print(f"Key {key_to_search} found in BST!")
else:
print(f"Key {key_to_search} not found in BST.")

Iterative Implementation

python
def search_bst_iterative(root, key):
while root is not None:
if key == root.key:
return root # Key found
elif key < root.key:
root = root.left # Move to the left subtree
else:
root = root.right # Move to the right subtree
return None # Key not found

# Example usage:
result = search_bst_iterative(root, key_to_search)

if result:
print(f"Key {key_to_search} found in BST!")
else:
print(f"Key {key_to_search} not found in BST.")

Time Complexity

  1. Best Case: O(1)O(1) — The key is found at the root.
  2. Average Case: O(log⁡n)O(\log n) — The height of the BST (assuming it is balanced).
  3. Worst Case: O(n)O(n) — The tree is skewed (all nodes in one branch).

Space Complexity

  • Recursive: O(h)O(h) — Due to the recursive call stack, where hh is the height of the tree.
  • Iterative: O(1)O(1) — No additional space is used beyond the variables.

Advantages of BST Search

  • Efficient for searching, especially in balanced BSTs.
  • Provides a logical framework for searching based on comparison.

Applications

  • Database indexing.
  • Auto-complete suggestions.
  • Implementing sets and maps in programming languages.

By leveraging the properties of a BST, the search process becomes both intuitive and efficient.

Related posts:

  1. What is the average typing speed for typists and enthusiasts
  2. What’s the Average Typing Speed? A Look at Typists and Enthusiasts
  3. Advantages and Disadvantages of Bus Topology
  4. First-order logic in Artificial Intelligence
  5. How to Track iPhone from an Android Phone
  6. Is Google translate accurate?
Previous article
What is OSI Model | 7 Layers Explained
Next article
How Fast is 400 km in miles per hour?
RELATED ARTICLES
0 0 votes
Article Rating

Leave a Reply

0 Comments
Oldest
Newest Most Voted
Inline Feedbacks
View all comments
- Advertisment -

Most Popular

Load more

Recent Comments

Ayo Emeka on What Tropical Fruits Begin With The Letter U?
Alison Jersey on Top 10 Greatest Kings in the World
Bethany Devson on How to Get Current Date and Time in Java
Emmanul Kingsley on What is Martin Luther King Jr’s favorite color?
Fred Phillip on How much is 26c to f?
0
Would love your thoughts, please comment.x
()
x
MORE STORIES

How do I create an HTML button that acts like a link?

Jonny - 0

Global and Local Variables in Python

Jason Smith - 0

Wanting a drawing tablet with screen. Which one do you recommend?

Anabelle Justin - 0