🔍 Searching in Binary Search Tree

Follow Me

🎯 Goal:

To find whether a value exists in the BST or not.

🔹 How it works:

Start from the root and compare:

• If value = current node → ✅ Found

• If value < current node → go to left

• If value > current node → go to right

• Repeat until found or reach a null (value not found)

🧠 Python Code:

def search(root, key): if root is None or root.val == key: return root if key < root.val: return search(root.left, key) return search(root.right, key)

🪴 Example BST:

We will search in this BST:

50 / \ 30 70 / \ / \ 20 40 60 80

🔍 Example Search:

✅ Search 40:

• 40 < 50 → go left

• 40 > 30 → go right

• 🎉 40 found!

❌ Search 90:

• 90 > 50 → go right

• 90 > 70 → go right

• 90 > 80 → go right → ❌ Not found (null)

📊 Time Complexity:

• Best / Avg case: O(log n)

• Worst case: O(n) (if tree is unbalanced)

🖼️ Simple Diagram for Searching 40:

50 / \ 30 70 / \ / \ 20 40 60 80 ↑ Found!