Show which keys a binary search tree looks at while it searches.
What to build
A search function that prints the path it takes through a binary search tree.
Requirements
- Build the tree by inserting the keys in the order given. A key that is already in the tree is ignored.
- For each target, print the keys visited, from the root down.
- End the line with
foundormissing.
Input
The first line has n, and the second has the n keys. The third line has q, and the fourth has the q targets.
Output
One line for each target: the keys visited, then found or missing, separated by spaces.
Constraints
1 ≤ n ≤ 100 and 1 ≤ q ≤ 100.
Example
Input:
6
50 30 70 20 40 60
2
40 65
Output:
50 30 40 found
50 70 60 missing
Why it works
A search never looks at both sides of a node. The path is one line from the root down, so its length is at most the height of the tree.
Examples
Example 1 · Input
6 50 30 70 20 40 60 2 40 65
Expected output
50 30 40 found 50 70 60 missing
Example 2 · Input
1 5 2 5 9
Expected output
5 found 5 missing
Hints
Hint 1
Start at the root, and print each key as you arrive at it.
Hint 2
If the key matches, print found. Otherwise go left for a smaller target and right for a larger one.
Hint 3
Falling off the tree at NULL means the key is missing.
Solution
Show one correct solution (try it yourself first)
#include <stdio.h>
#include <stdlib.h>
typedef struct tree {
int key;
struct tree *left, *right;
} Tree;
Tree *insert(Tree *t, int key) {
if (t == NULL) {
Tree *n = malloc(sizeof(Tree));
n->key = key;
n->left = NULL;
n->right = NULL;
return n;
}
if (key < t->key) t->left = insert(t->left, key);
else if (key > t->key) t->right = insert(t->right, key);
return t;
}
void search(Tree *t, int key) {
while (t != NULL) {
printf("%d ", t->key);
if (key == t->key) {
printf("found\n");
return;
}
t = key < t->key ? t->left : t->right;
}
printf("missing\n");
}
void free_tree(Tree *t) {
if (t == NULL) return;
free_tree(t->left);
free_tree(t->right);
free(t);
}
int main(void) {
int n, q;
scanf("%d", &n);
Tree *root = NULL;
for (int i = 0; i < n; i++) {
int key;
scanf("%d", &key);
root = insert(root, key);
}
scanf("%d", &q);
for (int i = 0; i < q; i++) {
int key;
scanf("%d", &key);
search(root, key);
}
free_tree(root);
return 0;
}