Tree Searching — Searching

🌳 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:

1. Every node has at most two children — left and right.
2. The left child always has a smaller value than the parent.
3. 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  80

Now let’s search for 40.

---

🧭 Step-by-Step Process

1. Start at the root (50)
   Compare your target value (40) with 50.
   Since 40 is smaller, move left.
2. Now at 30
   Compare again.
   40 is greater than 30 → move right.
3. 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:

1. Start at the root node.
2. If the root is empty, stop — it’s not there.
3. If the value matches the root’s value, you’ve found it!
4. If the value is smaller, search in the left subtree.
5. If the value is greater, search in the right subtree.
6. 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

---