Tree Search

A Binary Search Tree (BST) is a dynamic, hierarchical data structure. The Tree Search algorithm leverages the properties of a BST to locate a key efficiently.

It's like a "smart" filing system. Each node in the tree acts as a decision point, directing you left or right based on how the key compares to the node's value.

BST Properties (The Golden Rules)

For any given node in a BST:

1. All keys in the left subtree are strictly smaller than the node's key.
2. All keys in the right subtree are strictly greater than the node's key.
3. The left and right subtrees are also BSTs.

How Tree Search Works?

Consider the following BST:

        8
       / \
      3   10
     / \    \
    1   6    14
       / \
      5   7

We want to search for Key = 7.

• Step 1: Start at the Root node (Value = 8).
  • Compare 7 with 8. Since 7 < 8, we move to the Left Child.
• Step 2: Current node is 3.
  • Compare 7 with 3. Since 7 > 3, we move to the Right Child.
• Step 3: Current node is 6.
  • Compare 7 with 6. Since 7 > 6, we move to the Right Child.
• Step 4: Current node is 7.
  • Compare 7 with 7. Match Found! Return this node.

What if the key is not in the tree?

If we searched for Key = 11, the path would be: 8 → (right) 10 → (right) 14. Since 11 < 14, we would move to the left child of 14, which is NULL. At this point, we stop and return NULL, indicating the key is not present.

Algorithm for Tree Search

Since trees are naturally recursive, a recursive implementation is the most elegant.

Algorithm: TreeSearch(root, key)
Input:  root - Pointer to the root node of the BST
        key - The element to find
Output: Pointer to the node containing the key, otherwise NULL

Step 1: START
Step 2: IF root == NULL OR root.key == key THEN
Step 3:     RETURN root
Step 4: IF key < root.key THEN
Step 5:     RETURN TreeSearch(root.left, key)   [Search left subtree]
Step 6: ELSE
Step 7:     RETURN TreeSearch(root.right, key)  [Search right subtree]
Step 8: END

Implementation in C Programming

Here is the complete C program, including building the example BST.

#include <stdio.h>
#include <stdlib.h>

// Define the structure of a Tree Node
typedef struct Node {
    int data;
    struct Node* left;
    struct Node* right;
} Node;

// Function to create a new node
Node* createNode(int data) {
    Node* newNode = (Node*)malloc(sizeof(Node));
    newNode->data = data;
    newNode->left = NULL;
    newNode->right = NULL;
    return newNode;
}

// Recursive Tree Search function
Node* treeSearch(Node* root, int key) {
    // Base case: If tree is empty or key is found at root
    if (root == NULL || root->data == key) {
        return root;
    }

    // If the key is smaller than root's data, search left
    if (key < root->data) {
        return treeSearch(root->left, key);
    } 
    // If the key is greater than root's data, search right
    else {
        return treeSearch(root->right, key);
    }
}

int main() {
    // Construct the BST from the example
    Node* root = createNode(8);
    root->left = createNode(3);
    root->right = createNode(10);
    root->left->left = createNode(1);
    root->left->right = createNode(6);
    root->right->right = createNode(14);
    root->left->right->left = createNode(5);
    root->left->right->right = createNode(7);

    int key = 7;
    Node* result = treeSearch(root, key);

    if (result != NULL) {
        printf("Element %d found in the Binary Search Tree.\n", key);
    } else {
        printf("Element %d not found in the Binary Search Tree.\n", key);
    }
    return 0;
}

Output:

Element 7 found in the Binary Search Tree.

Time and Space Complexity Analysis

Time Complexity

The time taken is directly proportional to the height (h) of the tree, because we traverse one level per comparison.

Space Complexity

• Recursive Version: O(h) – where h is the height of the tree, due to the function call stack. In the worst case (skewed), this is O(n).

Advantages of Tree Search

1. Dynamic Structure: Unlike Binary Search on arrays, Tree Search allows you to insert and delete elements without shifting other elements.
2. Maintains Sorted Order: Inorder traversal of a BST always gives a sorted list.
3. Versatile: Supports other useful operations like finding the minimum, maximum, and range queries.

Disadvantages of Tree Search

1. Worst-Case Degradation: If the tree becomes skewed, it performs no better than Linear Search (O(n)).
2. Memory Overhead: Each node requires extra memory for two pointers (left and right), unlike arrays.
3. Complexity: Implementing a fully self-balancing BST (like AVL or Red-Black) is complex, though standard BSTs are simple.

When to Use Tree Search?

• When data is highly dynamic (frequent insertions and deletions).
• When you need to maintain sorted data in real-time.
• When you need to perform range queries (e.g., "Find all employees with ages between 25 and 40").
• When you prefer a recursive, elegant structure over rigid arrays.

Real-World Analogy

Imagine a "choose your own adventure" book where every decision point tells you to go to page 50 or page 100. You don't read linearly; you follow the decision rules that eliminate huge chunks of the book instantly. 

The BST is that decision tree each node asks, "Is the key smaller or larger?" and guides you down the correct path, bypassing all irrelevant data.