Linear Search in C, C++, Java & Python – Code with Explanation & Examples in Short and Simple

   

C Program

#include <stdio.h>
#include <stdlib.h>
typedef struct N { int d; struct N *l, *r; } N;
N* ins(N* r, int v) {
    if (!r) { r = malloc(sizeof(N)); r->d = v; r->l = r->r = NULL; return r; }
    if (v < r->d) r->l = ins(r->l, v); else if (v > r->d) r->r = ins(r->r, v);
    return r;
}
int src(N* r, int k) {
    if (!r) return 0;
    if (r->d == k) return 1;
    return k < r->d ? src(r->l, k) : src(r->r, k);
}
int main() {
    int a[] = {5,3,7,2,4}, k = 4, i; N* r = NULL;
    for (i = 0; i < 5; i++) r = ins(r, a[i]);
    printf(src(r, k) ? "Found" : "Not Found");
}

C Output

Input:
Array: 5 3 7 2 4
Search: 4
Output:
Found

C++ Program

#include <iostream>
using namespace std;
struct N { int d; N *l, *r; N(int v) : d(v), l(0), r(0) {} };
N* ins(N* r, int v) {
    if (!r) return new N(v);
    if (v < r->d) r->l = ins(r->l, v); else if (v > r->d) r->r = ins(r->r, v);
    return r;
}
bool src(N* r, int k) {
    if (!r) return false;
    if (r->d == k) return true;
    return k < r->d ? src(r->l, k) : src(r->r, k);
}
int main() {
    int a[] = {8, 4, 10, 2, 6}, k = 6;
    N* r = nullptr;
    for (int i : a) r = ins(r, i);
    cout << (src(r, k) ? "Found" : "Not Found");
}

C++ Output

Input:
Array: 8 4 10 2 6
Search: 6
Output:
Found

JAVA Program

class Node {
    int d; Node l, r;
    Node(int d) { this.d = d; }
}
public class Main {
    static Node ins(Node r, int v) {
        if (r == null) return new Node(v);
        if (v < r.d) r.l = ins(r.l, v); else if (v > r.d) r.r = ins(r.r, v);
        return r;
    }
    static boolean src(Node r, int k) {
        if (r == null) return false;
        if (r.d == k) return true;
        return k < r.d ? src(r.l, k) : src(r.r, k);
    }
    public static void main(String[] args) {
        int[] a = {9, 5, 12, 3, 6}; int k = 12;
        Node r = null;
        for (int v : a) r = ins(r, v);
        System.out.println(src(r, k) ? "Found" : "Not Found");
    }
}

JAVA Output

Input:
Array: 9 5 12 3 6
Search: 12
Output:
Found

Python Program

class N:
    def __init__(s, d): s.d, s.l, s.r = d, None, None
def ins(r, v):
    if not r: return N(v)
    if v < r.d: r.l = ins(r.l, v)
    elif v > r.d: r.r = ins(r.r, v)
    return r
def src(r, k):
    if not r: return False
    if r.d == k: return True
    return src(r.l, k) if k < r.d else src(r.r, k)

a = [7, 3, 9, 1, 4]; k = 2
r = None
for v in a: r = ins(r, v)
print("Found" if src(r, k) else "Not Found")

Python Output

Input:
Array: 7 3 9 1 4
Search: 2
Output:
Not Found

In-Depth Explanation

Example

Suppose we take the Python example. We put the numbers 7, 3, 9, 1, 4 into a BST. The structure is:

        7

       / \

      3   9

     / \

    1   4

When we look for 2, it's not present in the tree, so the output is: Not Found. If we have looked for 4, it could be easily located by going left → right.

Real-Life Analogy

Imagine your phonebook sorted alphabetically. To locate a contact, you don't read through all of them — you jump to the proper alphabetical section instantly. That's the principle of BST — it's sorted, so you can quickly skip unnecessary sections of data.

Why It Matters

BSTs are essential in:

Quick lookups

Preserving sorted data

Efficient insert/search operations (O(log n) on average)

Constructing index trees in databases, filesystems, and compilers

BSTs ensure performance doesn’t degrade with larger data, which makes them suitable for scalable apps.

Learning Insights

This problem teaches you:

Recursive thinking

How to build a tree structure using classes/structs

Insertion rules: left < node < right

Recursive search logic and tree traversal

It also helps strengthen your understanding of data structures and memory allocation (especially in C/C++ with malloc/new).

Interview & Real-World Use

In interviews, this is a classic problem that tests:

Tree data structures

Recursion skills

Knowledge of sorting/searching logic

In practical applications, BSTs are employed in:

Compilers and interpreters

Database indexing

Autocomplete search systems

Memory management systems

Binary Search Tree insertion and search operations form the basis of optimized data processing. Whether you are creating a database, search engine, or an optimized data store, understanding BSTs is crucial. The C, C++, Java, and Python solutions given here are the most concise, elegant versions created to help the logic be easily understood by any student or budding software developer.