Trees

BST Search

Search a binary search tree for one present and one absent value.

Algorithm

Basic Implementation

basic.c 
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
typedef struct Node { int value; struct Node* left; struct Node* right; } Node;
Node* node_new(int value, Node* left, Node* right) {
    Node* node = (Node*)malloc(sizeof(Node));
    node->value = value; node->left = left; node->right = right; return node;
}
void append(char* out, const char* text) { strcat(out, text); }
void render(Node* node, char* out) {
    char buf[16];
    if (node == NULL) { append(out, "_"); return; }
    sprintf(buf, "%d", node->value); append(out, buf);
    if (node->left != NULL || node->right != NULL) {
        append(out, "("); render(node->left, out); append(out, ","); render(node->right, out); append(out, ")");
    }
}
Node* sample_tree(void) {
    return node_new(4, node_new(2, node_new(1, NULL, NULL), node_new(3, NULL, NULL)),
                       node_new(6, node_new(5, NULL, NULL), node_new(7, NULL, NULL)));
}
void print_list(int* values, int n) {
    printf("[");
    for (int i = 0; i < n; i++) { if (i) printf(", "); printf("%d", values[i]); }
    printf("]\n");
}
int search(Node* root, int target) { Node* node = root; while (node) { if (target == node->value) return 1; node = target < node->value ? node->left : node->right; } return 0; }
int main(void) { Node* root = sample_tree(); printf("%s\n", search(root, 5) ? "5 found" : "5 not found"); printf("%s\n", search(root, 8) ? "8 found" : "8 not found"); }

A BST search follows one comparison path. The same pinned tree shows a found path for 5 and a missing path for 8.

Step 1 - Find 5

Search 5 takes right from 4, then left from 6, then matches 5.

Present search path: 4 -> 6 -> 5.4#126#2135match7

Step 2 - Miss 8

Search 8 takes right from 4, right from 6, right from 7, then reaches null.

Absent search path: 4 -> 6 -> 7 -> null.4#126#21357#3nullnot found

Complexity

  • Time: O(h) per search
  • Space: O(1) iterative

Implementation notes

  • C defines typedef struct Node { int value; struct Node* left; struct Node* right; } Node, with raw child pointers that are either NULL or point at heap-allocated nodes.
  • sample_tree() builds 4(2(1,3),6(5,7)) through nested node_new calls; node_new uses malloc(sizeof(Node)), and this checked executable does not free those nodes.
  • search(Node* root, int target) uses an iterative Node* node cursor. It returns 1 on target == node->value, otherwise follows left or right until the cursor becomes NULL, then returns 0.
  • The search helper reads pointers and scalar values only; it does not mutate root, child links, or node contents.
  • The trace for target 5 follows 4 -> right, 6 -> left, then matches 5. The trace for target 8 follows 4 -> right, 6 -> right, 7 -> right, then reaches NULL and reports not found.
  • main prints the boolean result through ternary string literals: 5 found and 8 not found on separate lines. Visible memory is heap nodes, stack cursor/target locals, and string literals.
search path A comparison chooses one subtree at each step, so whole branches are skipped.