🌳 Searching (Tree Searching)
Let’s start with a simple question:
If you wanted to find a person’s name in a family tree, what would you do?
You wouldn’t start looking from the youngest baby, right?
You’d begin at the top ancestor (root) and then move down the branches — left or right — until you reach the person you’re looking for.
That’s the basic idea behind Tree Searching in data structures.
It’s all about finding a specific node (or value) inside a tree by starting from the root node and moving in the right direction step by step.
🌿 What Is a Tree? (Quick Recap)
A tree is a way to store data in a connected, branching structure — kind of like an upside-down family tree.
It has:
- A root (the top node),
- Branches (links to child nodes),
- And leaves (nodes with no children).
When we talk about searching in a tree, we usually mean searching in a Binary Search Tree (BST) because it’s designed to make searching fast and easy.
🌲 Binary Search Tree (BST) Rules
In a Binary Search Tree:
- Every node has at most two children — left and right.
- The left child always has a smaller value than the parent.
- The right child always has a larger value than the parent.
This ordering is what makes searching efficient — just like how a dictionary is arranged alphabetically.
🔍 The Idea Behind Tree Searching
Tree Searching is like asking questions to narrow down where the value might be.
For example, imagine this Binary Search Tree:
50
/ \
30 70
/ \ / \
20 40 60 80Now let’s search for 40.
🧭 Step-by-Step Process
- Start at the root (50)
Compare your target value (40) with 50.
Since 40 is smaller, move left. - Now at 30
Compare again.
40 is greater than 30 → move right. - Now at 40
Bingo! You’ve found the value 🎯
Notice how we didn’t check every node — we only followed the path that made sense based on comparisons.
📘 Diagram: Searching in a Binary Search Tree
[50]
/ \
[30] [70]
/ \ / \
[20] [40] [60] [80]
↑
Searching for 40:
- 40 < 50 → go left
- 40 > 30 → go right
- Found at 40 ✅This step-by-step movement down the tree is what we call Tree Searching.
💡 A Simple Real-Life Analogy
Think of a bookshelf organized by book numbers.
If you’re looking for book number 40 and you know:
- Left side has smaller numbers,
- Right side has larger numbers,
Then you’ll never waste time checking every single book — you’ll just follow the clues until you reach 40.
That’s exactly how a BST works!
⚙️ Tree Searching Algorithm (in plain words)
Here’s how you can think of it logically:
- Start at the root node.
- If the root is empty, stop — it’s not there.
- If the value matches the root’s value, you’ve found it!
- If the value is smaller, search in the left subtree.
- If the value is greater, search in the right subtree.
- Keep repeating until you find it or run out of nodes.
✏️ Pseudocode (Simplified)
TreeSearch(root, key):
if root is NULL:
return "Not Found"
if key == root.value:
return "Found"
if key < root.value:
return TreeSearch(root.left, key)
else:
return TreeSearch(root.right, key)This recursive method keeps exploring down the correct branch until the key is found (or not).
⏱️ Time Complexity
| Case | Time | Explanation |
|---|---|---|
| Best | O(1) | Found at the root |
| Average | O(log n) | Balanced tree, halves each step |
| Worst | O(n) | Skewed tree (like a linked list) |
If the tree is balanced, searching is super fast.
But if all elements lean to one side (like 10 → 20 → 30 → 40…), it slows down.
🌻 Advantages
✅ Faster than linear or sequential searching.
✅ Works great for sorted data.
✅ Easy to understand and implement.
🍂 Limitations
❌ Only works efficiently if the tree is balanced.
❌ Extra memory is needed for storing links between nodes.
❌ In the worst case, can degrade to linear time.
🌈 Quick Recap
| Concept | Meaning |
|---|---|
| Tree Searching | Finding a value in a tree by moving left or right based on comparisons |
| Best Tree Type | Binary Search Tree |
| Speed | Very fast when the tree is balanced |
| Real-life Example | Looking for a word in a dictionary or a name in a sorted contact list |
About the Author
