Search

Definition

Search in a tree is the process of visiting nodes systematically to find a node containing a specified value or key. The goal is to determine whether the element exists in the tree and, if so, return its location or reference.

In a Binary Search Tree (BST), search is performed by comparing the target value with the current node and moving left or right accordingly:

• If the target is smaller, go to the left subtree.
• If the target is larger, go to the right subtree.
• If it matches, the element is found.

Main Content

1. Tree Search Concept

• Search in a tree is not always done by checking every node one by one; instead, it often uses the tree’s structure to reduce the number of comparisons.
• The search method depends on the type of tree. For example, in a general tree, traversal-based search may be needed, while in a Binary Search Tree, directed search is used based on ordering rules.

A tree search begins usually from the root node. From there, the algorithm decides which path to follow depending on the tree’s properties. If the tree is ordered, the search becomes more efficient because each comparison eliminates a large portion of the tree.

Example: If you search for 50 in a Binary Search Tree:

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

• Start at 40
• 50 > 40, move right to 60
• 50 < 60, move left to 50
• Found the target

This is much faster than checking every node in the tree.

2. Binary Search Tree Search Concept

• A Binary Search Tree is specially designed for efficient searching because it keeps smaller values on the left and larger values on the right.
• Search in a BST follows a recursive or iterative comparison process, which usually takes time proportional to the height of the tree.

The search algorithm in a BST works as follows:

1. Compare the target value with the root.
2. If equal, the search is successful.
3. If the target is smaller, search the left subtree.
4. If the target is larger, search the right subtree.
5. Repeat until the value is found or the subtree becomes empty.

Example: Search for 25 in the following BST:

        15
       /  \
      10   25
     / \   / \
    8  12 20 30

• Start at 15
• 25 > 15, go right
• At 25, match found

Time complexity:

• Best case: O(1) if found at the root
• Average case: O(log n) for a balanced BST
• Worst case: O(n) for a skewed BST

This makes balancing very important for performance.

3. Traversal-Based Search Concept

• In trees that do not maintain ordering, such as general trees or binary trees without BST properties, search is often performed using traversals.
• Traversal-based search means visiting nodes in a systematic order until the target is found.

Common traversal methods include:

• Preorder: Root → Left → Right
• Inorder: Left → Root → Right
• Postorder: Left → Right → Root
• Level order: Level by level from top to bottom

Example of traversal-based search: If the tree is:

        A
       / \
      B   C
     / \   \
    D   E   F

To search for E using preorder:

• Visit A
• Visit B
• Visit D
• Backtrack to E
• Found

Traversal-based search may require visiting many or even all nodes in the worst case. It is useful when the tree does not provide ordering information.

Working / Process

1. Start from the root node
2. The search begins at the root because it is the entry point to the tree.

3. In a BST, the root determines the next direction of movement based on comparison.

4. Compare the target with the current node

5. If the current node contains the target, stop and report success.
6. If not, decide the next node to visit.

7. In ordered trees, the comparison tells whether to go left or right.

8. Move through the tree until the result is determined

9. Continue moving through the appropriate subtree in BST search.
10. In traversal-based search, visit nodes one by one according to the traversal order.
11. If the target is found, return it; if the subtree ends or all nodes are checked, report that the item is not present.

Advantages / Applications

• Efficient data retrieval in ordered trees, especially Binary Search Trees, where search can be much faster than linear search.
• Used in real-world systems such as databases, directory structures, symbol tables, routing tables, and file indexing.
• Supports fast decision-making in algorithms by quickly checking whether a value, key, or record exists.

Summary

• Search in a tree means finding a node or value by systematically checking nodes.
• In a BST, comparison-based movement makes search efficient.
• Traversal-based search is used when the tree has no ordering rule.
• Important terms to remember: root, node, subtree, Binary Search Tree, traversal, comparison, height.