Intermediate

#include <stdio.h>

int binary_search(int arr[], int size, int target) {
    // => arr must be sorted in ascending order for binary search to work
    // => target is the value we want to find

    int left = 0, right = size - 1;
    // => left starts at index 0, right starts at last valid index
    // => these two pointers define the active search window

    while (left <= right) {
        // => loop continues as long as search window is non-empty
        // => when left > right the target is not in the array

        int mid = left + (right - left) / 2;
        // => mid is the index of the middle element
        // => use (right - left) / 2 instead of (left + right) / 2 to avoid integer overflow

        if (arr[mid] == target) {
            // => found the target — return its index immediately
            return mid;
        } else if (arr[mid] < target) {
            // => mid element is too small, target must be to the right
            left = mid + 1;
            // => discard left half including mid
        } else {
            // => mid element is too large, target must be to the left
            right = mid - 1;
            // => discard right half including mid
        }
    }

    return -1;
    // => target not found, return sentinel value -1
}

int main(void) {
    int arr[] = {2, 5, 8, 12, 16, 23, 38, 56, 72, 91};
    // => sorted array with 10 elements, indices 0-9
    int size = sizeof(arr) / sizeof(arr[0]);

    printf("%d\n", binary_search(arr, size, 23));   // => Output: 5  (arr[5] == 23)
    printf("%d\n", binary_search(arr, size, 100));  // => Output: -1 (100 not in array)
    printf("%d\n", binary_search(arr, size, 2));    // => Output: 0  (first element)
    printf("%d\n", binary_search(arr, size, 91));   // => Output: 9  (last element)
    return 0;
}

package main

import "fmt"

func binarySearch(arr []int, target int) int {
    // => arr must be sorted in ascending order for binary search to work
    // => target is the value we want to find

    left, right := 0, len(arr)-1
    // => left starts at index 0, right starts at last valid index
    // => these two pointers define the active search window

    for left <= right {
        // => loop continues as long as search window is non-empty
        // => when left > right the target is not in the array

        mid := left + (right-left)/2
        // => mid is the index of the middle element
        // => use (right - left) / 2 instead of (left + right) / 2 to avoid integer overflow

        if arr[mid] == target {
            // => found the target — return its index immediately
            return mid
        } else if arr[mid] < target {
            // => mid element is too small, target must be to the right
            left = mid + 1
            // => discard left half including mid
        } else {
            // => mid element is too large, target must be to the left
            right = mid - 1
            // => discard right half including mid
        }
    }

    return -1
    // => target not found, return sentinel value -1
}

func main() {
    arr := []int{2, 5, 8, 12, 16, 23, 38, 56, 72, 91}
    // => sorted array with 10 elements, indices 0-9

    fmt.Println(binarySearch(arr, 23))  // => Output: 5  (arr[5] == 23)
    fmt.Println(binarySearch(arr, 100)) // => Output: -1 (100 not in array)
    fmt.Println(binarySearch(arr, 2))   // => Output: 0  (first element)
    fmt.Println(binarySearch(arr, 91))  // => Output: 9  (last element)
}

def binary_search(arr, target):
    # => arr must be sorted in ascending order for binary search to work
    # => target is the value we want to find

    left, right = 0, len(arr) - 1
    # => left starts at index 0, right starts at last valid index
    # => these two pointers define the active search window

    while left <= right:
        # => loop continues as long as search window is non-empty
        # => when left > right the target is not in the array

        mid = left + (right - left) // 2
        # => mid is the index of the middle element
        # => use (right - left) // 2 instead of (left + right) // 2 to avoid integer overflow

        if arr[mid] == target:
            # => found the target — return its index immediately
            return mid
        elif arr[mid] < target:
            # => mid element is too small, target must be to the right
            left = mid + 1
            # => discard left half including mid
        else:
            # => mid element is too large, target must be to the left
            right = mid - 1
            # => discard right half including mid

    return -1
    # => target not found, return sentinel value -1


arr = [2, 5, 8, 12, 16, 23, 38, 56, 72, 91]
# => sorted array with 10 elements, indices 0-9

print(binary_search(arr, 23))   # => Output: 5  (arr[5] == 23)
print(binary_search(arr, 100))  # => Output: -1 (100 not in array)
print(binary_search(arr, 2))    # => Output: 0  (first element)
print(binary_search(arr, 91))   # => Output: 9  (last element)

public class BinarySearch {
    static int binarySearch(int[] arr, int target) {
        // => arr must be sorted in ascending order for binary search to work
        // => target is the value we want to find

        int left = 0, right = arr.length - 1;
        // => left starts at index 0, right starts at last valid index
        // => these two pointers define the active search window

        while (left <= right) {
            // => loop continues as long as search window is non-empty
            // => when left > right the target is not in the array

            int mid = left + (right - left) / 2;
            // => mid is the index of the middle element
            // => use (right - left) / 2 instead of (left + right) / 2 to avoid integer overflow

            if (arr[mid] == target) {
                // => found the target — return its index immediately
                return mid;
            } else if (arr[mid] < target) {
                // => mid element is too small, target must be to the right
                left = mid + 1;
                // => discard left half including mid
            } else {
                // => mid element is too large, target must be to the left
                right = mid - 1;
                // => discard right half including mid
            }
        }

        return -1;
        // => target not found, return sentinel value -1
    }

    public static void main(String[] args) {
        int[] arr = {2, 5, 8, 12, 16, 23, 38, 56, 72, 91};
        // => sorted array with 10 elements, indices 0-9

        System.out.println(binarySearch(arr, 23));   // => Output: 5  (arr[5] == 23)
        System.out.println(binarySearch(arr, 100));  // => Output: -1 (100 not in array)
        System.out.println(binarySearch(arr, 2));    // => Output: 0  (first element)
        System.out.println(binarySearch(arr, 91));   // => Output: 9  (last element)
    }
}

#include <stdio.h>

int search_insert_position(int arr[], int size, int target) {
    // => returns index where target is found, or where it should be inserted
    // => result is always in range [0, size] inclusive

    int left = 0, right = size;
    // => right is size, not size-1, because insertion can happen at end

    while (left < right) {
        // => strict less-than: when left == right the window is one slot wide
        int mid = left + (right - left) / 2;
        // => floor-division always rounds toward zero, biasing toward left

        if (arr[mid] < target) {
            // => mid is strictly less than target, so insert position is right of mid
            left = mid + 1;
        } else {
            // => arr[mid] >= target: insertion point is at mid or to its left
            right = mid;
            // => do NOT subtract 1; mid is a candidate for insertion position
        }
    }

    return left;
    // => left == right at loop exit, which is the insertion index
}

int main(void) {
    int arr[] = {1, 3, 5, 6};
    int size = 4;
    printf("%d\n", search_insert_position(arr, size, 5));  // => Output: 2  (found at index 2)
    printf("%d\n", search_insert_position(arr, size, 2));  // => Output: 1  (2 goes between 1 and 3)
    printf("%d\n", search_insert_position(arr, size, 7));  // => Output: 4  (7 appended at end)
    printf("%d\n", search_insert_position(arr, size, 0));  // => Output: 0  (0 prepended at start)
    return 0;
}

package main

import "fmt"

func searchInsertPosition(arr []int, target int) int {
    // => returns index where target is found, or where it should be inserted
    // => result is always in range [0, len(arr)] inclusive

    left, right := 0, len(arr)
    // => right is len(arr), not len(arr)-1, because insertion can happen at end

    for left < right {
        // => strict less-than: when left == right the window is one slot wide
        mid := left + (right-left)/2
        // => floor-division always rounds toward zero, biasing toward left

        if arr[mid] < target {
            // => mid is strictly less than target, so insert position is right of mid
            left = mid + 1
        } else {
            // => arr[mid] >= target: insertion point is at mid or to its left
            right = mid
            // => do NOT subtract 1; mid is a candidate for insertion position
        }
    }

    return left
    // => left == right at loop exit, which is the insertion index
}

func main() {
    arr := []int{1, 3, 5, 6}
    fmt.Println(searchInsertPosition(arr, 5)) // => Output: 2  (found at index 2)
    fmt.Println(searchInsertPosition(arr, 2)) // => Output: 1  (2 goes between 1 and 3)
    fmt.Println(searchInsertPosition(arr, 7)) // => Output: 4  (7 appended at end)
    fmt.Println(searchInsertPosition(arr, 0)) // => Output: 0  (0 prepended at start)
}

def search_insert_position(arr, target):
    # => returns index where target is found, or where it should be inserted
    # => result is always in range [0, len(arr)] inclusive

    left, right = 0, len(arr)
    # => right is len(arr), not len(arr)-1, because insertion can happen at end

    while left < right:
        # => strict less-than: when left == right the window is one slot wide
        mid = left + (right - left) // 2
        # => floor-division always rounds toward zero, biasing toward left

        if arr[mid] < target:
            # => mid is strictly less than target, so insert position is right of mid
            left = mid + 1
        else:
            # => arr[mid] >= target: insertion point is at mid or to its left
            right = mid
            # => do NOT subtract 1; mid is a candidate for insertion position

    return left
    # => left == right at loop exit, which is the insertion index


arr = [1, 3, 5, 6]
print(search_insert_position(arr, 5))  # => Output: 2  (found at index 2)
print(search_insert_position(arr, 2))  # => Output: 1  (2 goes between 1 and 3)
print(search_insert_position(arr, 7))  # => Output: 4  (7 appended at end)
print(search_insert_position(arr, 0))  # => Output: 0  (0 prepended at start)

public class SearchInsertPosition {
    static int searchInsertPosition(int[] arr, int target) {
        // => returns index where target is found, or where it should be inserted
        // => result is always in range [0, arr.length] inclusive

        int left = 0, right = arr.length;
        // => right is arr.length, not arr.length-1, because insertion can happen at end

        while (left < right) {
            // => strict less-than: when left == right the window is one slot wide
            int mid = left + (right - left) / 2;
            // => floor-division always rounds toward zero, biasing toward left

            if (arr[mid] < target) {
                // => mid is strictly less than target, so insert position is right of mid
                left = mid + 1;
            } else {
                // => arr[mid] >= target: insertion point is at mid or to its left
                right = mid;
                // => do NOT subtract 1; mid is a candidate for insertion position
            }
        }

        return left;
        // => left == right at loop exit, which is the insertion index
    }

    public static void main(String[] args) {
        int[] arr = {1, 3, 5, 6};
        System.out.println(searchInsertPosition(arr, 5));  // => Output: 2  (found at index 2)
        System.out.println(searchInsertPosition(arr, 2));  // => Output: 1  (2 goes between 1 and 3)
        System.out.println(searchInsertPosition(arr, 7));  // => Output: 4  (7 appended at end)
        System.out.println(searchInsertPosition(arr, 0));  // => Output: 0  (0 prepended at start)
    }
}

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

#define CAPACITY 8

typedef struct Entry {
    char key[64];
    int value;
    struct Entry *next;
    // => each entry points to the next in its chain (linked list)
} Entry;

typedef struct {
    Entry *buckets[CAPACITY];
    // => each bucket is the head of a linked list (chain) of entries
    int size;
    // => tracks number of key-value pairs stored
} HashTable;

unsigned int hash_func(const char *key) {
    unsigned int h = 0;
    while (*key) {
        h = h * 31 + (unsigned char)(*key);
        key++;
    }
    return h % CAPACITY;
    // => simple polynomial hash mapped to a valid bucket index [0, CAPACITY-1]
}

void ht_init(HashTable *ht) {
    for (int i = 0; i < CAPACITY; i++) {
        ht->buckets[i] = NULL;
    }
    ht->size = 0;
}

void ht_put(HashTable *ht, const char *key, int value) {
    unsigned int idx = hash_func(key);
    // => idx is the target bucket index
    Entry *cur = ht->buckets[idx];
    // => retrieve the chain at that bucket

    while (cur) {
        if (strcmp(cur->key, key) == 0) {
            cur->value = value;
            // => update existing key's value in-place
            return;
        }
        cur = cur->next;
    }

    Entry *e = (Entry *)malloc(sizeof(Entry));
    // => key not found in chain: create new entry
    strcpy(e->key, key);
    e->value = value;
    e->next = ht->buckets[idx];
    ht->buckets[idx] = e;
    // => prepend new entry to the chain
    ht->size++;
    // => increment count of stored pairs
}

int ht_get(HashTable *ht, const char *key, int *found) {
    unsigned int idx = hash_func(key);
    // => compute bucket index for this key
    Entry *cur = ht->buckets[idx];
    while (cur) {
        if (strcmp(cur->key, key) == 0) {
            *found = 1;
            return cur->value;
            // => found key: return its associated value
        }
        cur = cur->next;
    }
    *found = 0;
    return 0;
    // => key not present in any chain
}

void ht_remove(HashTable *ht, const char *key) {
    unsigned int idx = hash_func(key);
    Entry *cur = ht->buckets[idx];
    Entry *prev = NULL;
    while (cur) {
        if (strcmp(cur->key, key) == 0) {
            if (prev) {
                prev->next = cur->next;
            } else {
                ht->buckets[idx] = cur->next;
            }
            free(cur);
            // => remove entry and free memory
            return;
        }
        prev = cur;
        cur = cur->next;
    }
}

int main(void) {
    HashTable ht;
    ht_init(&ht);
    ht_put(&ht, "apple", 1);
    ht_put(&ht, "banana", 2);
    ht_put(&ht, "cherry", 3);
    ht_put(&ht, "banana", 99);    // => update existing key

    int found;
    printf("%d\n", ht_get(&ht, "apple", &found));   // => Output: 1
    printf("%d\n", ht_get(&ht, "banana", &found));   // => Output: 99 (updated value)
    ht_get(&ht, "grape", &found);
    printf("%s\n", found ? "found" : "None");         // => Output: None (not present)
    return 0;
}

package main

import "fmt"

const capacity = 8

type entry struct {
    key   string
    value int
    next  *entry
    // => each entry points to the next in its chain (linked list)
}

type HashTable struct {
    buckets [capacity]*entry
    // => each bucket is the head of a linked list (chain) of entries
    size int
    // => tracks number of key-value pairs stored
}

func hashFunc(key string) int {
    h := 0
    for _, c := range key {
        h = h*31 + int(c)
    }
    return h % capacity
    // => simple polynomial hash mapped to a valid bucket index [0, capacity-1]
}

func (ht *HashTable) Put(key string, value int) {
    idx := hashFunc(key)
    // => idx is the target bucket index
    cur := ht.buckets[idx]
    // => retrieve the chain at that bucket

    for cur != nil {
        if cur.key == key {
            cur.value = value
            // => update existing key's value in-place
            return
        }
        cur = cur.next
    }

    e := &entry{key: key, value: value, next: ht.buckets[idx]}
    // => key not found in chain: prepend new entry
    ht.buckets[idx] = e
    ht.size++
    // => increment count of stored pairs
}

func (ht *HashTable) Get(key string) (int, bool) {
    idx := hashFunc(key)
    // => compute bucket index for this key
    cur := ht.buckets[idx]
    for cur != nil {
        if cur.key == key {
            return cur.value, true
            // => found key: return its associated value
        }
        cur = cur.next
    }
    return 0, false
    // => key not present in any chain
}

func (ht *HashTable) Remove(key string) {
    idx := hashFunc(key)
    cur := ht.buckets[idx]
    var prev *entry
    for cur != nil {
        if cur.key == key {
            if prev != nil {
                prev.next = cur.next
            } else {
                ht.buckets[idx] = cur.next
            }
            return
        }
        prev = cur
        cur = cur.next
    }
}

func main() {
    ht := &HashTable{}
    ht.Put("apple", 1)
    ht.Put("banana", 2)
    ht.Put("cherry", 3)
    ht.Put("banana", 99) // => update existing key

    v, _ := ht.Get("apple")
    fmt.Println(v) // => Output: 1
    v, _ = ht.Get("banana")
    fmt.Println(v) // => Output: 99 (updated value)
    _, ok := ht.Get("grape")
    if !ok {
        fmt.Println("None") // => Output: None (not present)
    }
}

class HashTable:
    def __init__(self, capacity=8):
        self.capacity = capacity
        # => number of buckets; prime numbers reduce collision clustering
        self.buckets = [[] for _ in range(capacity)]
        # => each bucket is a list (chain) of (key, value) pairs
        # => initially all buckets are empty lists
        self.size = 0
        # => tracks number of key-value pairs stored

    def _hash(self, key):
        return hash(key) % self.capacity
        # => Python's built-in hash() returns an integer for any hashable key
        # => modulo maps that integer to a valid bucket index [0, capacity-1]

    def put(self, key, value):
        idx = self._hash(key)
        # => idx is the target bucket index
        bucket = self.buckets[idx]
        # => retrieve the chain at that bucket

        for i, (k, v) in enumerate(bucket):
            # => scan the chain to check if key already exists
            if k == key:
                bucket[i] = (key, value)
                # => update existing key's value in-place
                return
        bucket.append((key, value))
        # => key not found in chain: append new pair
        self.size += 1
        # => increment count of stored pairs

    def get(self, key):
        idx = self._hash(key)
        # => compute bucket index for this key
        for k, v in self.buckets[idx]:
            # => scan the chain at that bucket
            if k == key:
                return v
                # => found key: return its associated value
        return None
        # => key not present in any chain: return None

    def remove(self, key):
        idx = self._hash(key)
        bucket = self.buckets[idx]
        # => get the chain where key would live
        self.buckets[idx] = [(k, v) for k, v in bucket if k != key]
        # => rebuild chain excluding the target key
        # => self.size decrement omitted for brevity


ht = HashTable()
ht.put("apple", 1)
ht.put("banana", 2)
ht.put("cherry", 3)
ht.put("banana", 99)    # => update existing key

print(ht.get("apple"))   # => Output: 1
print(ht.get("banana"))  # => Output: 99 (updated value)
print(ht.get("grape"))   # => Output: None (not present)

import java.util.LinkedList;

public class HashTableChaining {
    static final int CAPACITY = 8;

    static class Entry {
        String key;
        int value;
        // => each entry stores a key-value pair
        Entry(String key, int value) {
            this.key = key;
            this.value = value;
        }
    }

    @SuppressWarnings("unchecked")
    LinkedList<Entry>[] buckets = new LinkedList[CAPACITY];
    // => each bucket is a linked list (chain) of entries
    int size = 0;
    // => tracks number of key-value pairs stored

    HashTableChaining() {
        for (int i = 0; i < CAPACITY; i++) {
            buckets[i] = new LinkedList<>();
        }
    }

    int hash(String key) {
        return Math.abs(key.hashCode()) % CAPACITY;
        // => Java's hashCode() returns an integer for any object
        // => modulo maps that integer to a valid bucket index [0, CAPACITY-1]
    }

    void put(String key, int value) {
        int idx = hash(key);
        // => idx is the target bucket index
        LinkedList<Entry> bucket = buckets[idx];
        // => retrieve the chain at that bucket

        for (Entry e : bucket) {
            if (e.key.equals(key)) {
                e.value = value;
                // => update existing key's value in-place
                return;
            }
        }
        bucket.add(new Entry(key, value));
        // => key not found in chain: append new pair
        size++;
        // => increment count of stored pairs
    }

    Integer get(String key) {
        int idx = hash(key);
        // => compute bucket index for this key
        for (Entry e : buckets[idx]) {
            if (e.key.equals(key)) {
                return e.value;
                // => found key: return its associated value
            }
        }
        return null;
        // => key not present in any chain: return null
    }

    void remove(String key) {
        int idx = hash(key);
        buckets[idx].removeIf(e -> e.key.equals(key));
        // => rebuild chain excluding the target key
    }

    public static void main(String[] args) {
        HashTableChaining ht = new HashTableChaining();
        ht.put("apple", 1);
        ht.put("banana", 2);
        ht.put("cherry", 3);
        ht.put("banana", 99);    // => update existing key

        System.out.println(ht.get("apple"));   // => Output: 1
        System.out.println(ht.get("banana"));  // => Output: 99 (updated value)
        System.out.println(ht.get("grape"));   // => Output: null (not present)
    }
}

#include <stdio.h>
#include <string.h>

#define MAX_WORDS 100
#define MAX_LEN 64

typedef struct {
    char key[MAX_LEN];
    int count;
} FreqEntry;

int count_with_array(const char *words[], int n, FreqEntry freq[], int *freq_size) {
    // => manual frequency counting using a flat array
    *freq_size = 0;

    for (int i = 0; i < n; i++) {
        // => iterate over every element in O(n) time
        int found = 0;
        for (int j = 0; j < *freq_size; j++) {
            if (strcmp(freq[j].key, words[i]) == 0) {
                freq[j].count++;
                // => increment count by 1
                found = 1;
                break;
            }
        }
        if (!found) {
            strcpy(freq[*freq_size].key, words[i]);
            freq[*freq_size].count = 1;
            (*freq_size)++;
            // => new word: add entry with count 1
        }
    }
    return *freq_size;
    // => returns number of distinct words
}

int main(void) {
    const char *words[] = {"apple", "banana", "apple", "cherry", "banana", "apple"};
    int n = 6;
    FreqEntry freq[MAX_WORDS];
    int freq_size;

    count_with_array(words, n, freq, &freq_size);
    printf("{");
    for (int i = 0; i < freq_size; i++) {
        if (i > 0) printf(", ");
        printf("'%s': %d", freq[i].key, freq[i].count);
    }
    printf("}\n");
    // => Output: {'apple': 3, 'banana': 2, 'cherry': 1}
    return 0;
}

package main

import "fmt"

func countWithMap(items []string) map[string]int {
    freq := make(map[string]int)
    // => empty map; will be populated key-by-key

    for _, item := range items {
        // => iterate over every element in O(n) time
        freq[item]++
        // => if key absent, Go zero-initialises to 0 then increments to 1
        // => if key present, simply increments existing count
    }
    return freq
    // => returns map[item]count
}

func main() {
    words := []string{"apple", "banana", "apple", "cherry", "banana", "apple"}

    result := countWithMap(words)
    fmt.Println(result)
    // => Output: map[apple:3 banana:2 cherry:1]
}

from collections import Counter, defaultdict

# Approach A: Manual dict counting
def count_with_dict(items):
    freq = {}
    # => empty dict; will be populated key-by-key

    for item in items:
        # => iterate over every element in O(n) time
        freq[item] = freq.get(item, 0) + 1
        # => freq.get(item, 0) returns current count or 0 if absent
        # => increment count by 1 and store back
    return freq
    # => returns {item: count, ...}


words = ["apple", "banana", "apple", "cherry", "banana", "apple"]
result = count_with_dict(words)
print(result)
# => Output: {'apple': 3, 'banana': 2, 'cherry': 1}

# Approach B: defaultdict — avoids the .get(key, 0) pattern
def count_with_defaultdict(items):
    freq = defaultdict(int)
    # => defaultdict(int) creates 0 automatically for missing keys

    for item in items:
        freq[item] += 1
        # => if key absent, freq[item] initialises to 0 then increments to 1
        # => if key present, simply increments existing count
    return dict(freq)
    # => convert back to plain dict for clean output


result2 = count_with_defaultdict(words)
print(result2)
# => Output: {'apple': 3, 'banana': 2, 'cherry': 1}

# Approach C: Counter — most Pythonic, adds extra utility methods
counter = Counter(words)
# => Counter is a dict subclass specialised for counting
# => single call replaces the manual loop entirely

print(counter.most_common(2))
# => Output: [('apple', 3), ('banana', 2)]  (top 2 by count)
print(counter["cherry"])   # => Output: 1
print(counter["grape"])    # => Output: 0  (missing keys return 0, not KeyError)

import java.util.HashMap;
import java.util.Map;

public class FrequencyCounting {
    static Map<String, Integer> countWithMap(String[] items) {
        Map<String, Integer> freq = new HashMap<>();
        // => empty map; will be populated key-by-key

        for (String item : items) {
            // => iterate over every element in O(n) time
            freq.put(item, freq.getOrDefault(item, 0) + 1);
            // => getOrDefault returns current count or 0 if absent
            // => increment count by 1 and store back
        }
        return freq;
        // => returns {item=count, ...}
    }

    public static void main(String[] args) {
        String[] words = {"apple", "banana", "apple", "cherry", "banana", "apple"};
        Map<String, Integer> result = countWithMap(words);
        System.out.println(result);
        // => Output: {apple=3, banana=2, cherry=1}
    }
}

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

typedef struct BSTNode {
    int val;
    // => node stores a single integer value
    struct BSTNode *left;
    // => left child: will hold values < val
    struct BSTNode *right;
    // => right child: will hold values > val
} BSTNode;

BSTNode *new_node(int val) {
    BSTNode *n = (BSTNode *)malloc(sizeof(BSTNode));
    n->val = val;
    n->left = NULL;
    n->right = NULL;
    return n;
}

BSTNode *bst_insert(BSTNode *root, int val) {
    if (root == NULL) {
        return new_node(val);
        // => base case: empty spot found, create new node here
    }
    if (val < root->val) {
        root->left = bst_insert(root->left, val);
        // => value belongs in left subtree; recurse and reattach
    } else if (val > root->val) {
        root->right = bst_insert(root->right, val);
        // => value belongs in right subtree; recurse and reattach
    }
    // => if val == root->val, duplicate — do nothing
    return root;
    // => return root so callers can chain insertions
}

int bst_search(BSTNode *root, int val) {
    if (root == NULL) {
        return 0;
        // => reached empty subtree: value not present in tree
    }
    if (val == root->val) {
        return 1;
        // => found exact match at current node
    } else if (val < root->val) {
        return bst_search(root->left, val);
        // => target smaller: must be in left subtree
    } else {
        return bst_search(root->right, val);
        // => target larger: must be in right subtree
    }
}

int main(void) {
    BSTNode *root = NULL;
    int values[] = {50, 30, 70, 20, 40, 60, 80};
    for (int i = 0; i < 7; i++) {
        root = bst_insert(root, values[i]);
        // => build tree one node at a time
    }

    printf("%s\n", bst_search(root, 40) ? "True" : "False");  // => Output: True  (40 is in tree)
    printf("%s\n", bst_search(root, 55) ? "True" : "False");  // => Output: False (55 not in tree)
    return 0;
}

package main

import "fmt"

type BSTNode struct {
    Val   int
    Left  *BSTNode
    Right *BSTNode
}

func bstInsert(root *BSTNode, val int) *BSTNode {
    if root == nil {
        return &BSTNode{Val: val}
        // => base case: empty spot found, create new node here
    }
    if val < root.Val {
        root.Left = bstInsert(root.Left, val)
        // => value belongs in left subtree; recurse and reattach
    } else if val > root.Val {
        root.Right = bstInsert(root.Right, val)
        // => value belongs in right subtree; recurse and reattach
    }
    // => if val == root.Val, duplicate — do nothing
    return root
    // => return root so callers can chain insertions
}

func bstSearch(root *BSTNode, val int) bool {
    if root == nil {
        return false
        // => reached empty subtree: value not present in tree
    }
    if val == root.Val {
        return true
        // => found exact match at current node
    } else if val < root.Val {
        return bstSearch(root.Left, val)
        // => target smaller: must be in left subtree
    } else {
        return bstSearch(root.Right, val)
        // => target larger: must be in right subtree
    }
}

func main() {
    var root *BSTNode
    for _, v := range []int{50, 30, 70, 20, 40, 60, 80} {
        root = bstInsert(root, v)
        // => build tree one node at a time
        // => final structure matches diagram above
    }

    fmt.Println(bstSearch(root, 40)) // => Output: true  (40 is in tree)
    fmt.Println(bstSearch(root, 55)) // => Output: false (55 not in tree)
}

class BSTNode:
    def __init__(self, val):
        self.val = val
        # => node stores a single integer value
        self.left = None
        # => left child: will hold values < self.val
        self.right = None
        # => right child: will hold values > self.val


def bst_insert(root, val):
    if root is None:
        return BSTNode(val)
        # => base case: empty spot found, create new node here

    if val < root.val:
        root.left = bst_insert(root.left, val)
        # => value belongs in left subtree; recurse and reattach
    elif val > root.val:
        root.right = bst_insert(root.right, val)
        # => value belongs in right subtree; recurse and reattach
    # => if val == root.val, duplicate — do nothing (ignore or update as needed)
    return root
    # => return root so callers can chain insertions


def bst_search(root, val):
    if root is None:
        return False
        # => reached empty subtree: value not present in tree

    if val == root.val:
        return True
        # => found exact match at current node
    elif val < root.val:
        return bst_search(root.left, val)
        # => target smaller: must be in left subtree
    else:
        return bst_search(root.right, val)
        # => target larger: must be in right subtree


root = None
for v in [50, 30, 70, 20, 40, 60, 80]:
    root = bst_insert(root, v)
    # => build tree one node at a time
    # => final structure matches diagram above

print(bst_search(root, 40))   # => Output: True  (40 is in tree)
print(bst_search(root, 55))   # => Output: False (55 not in tree)