Challenge: The Search Path

Lab Java Beginner 10 points

Build a BST by inserting n numbers in the given order. Then for each query, print the values visited while searching for it, separated by spaces, followed by found or missing.

Input

Line 1: n. Line 2: n different whole numbers. Line 3: q. Line 4: q numbers to search.

Output

One line per query, like 50 30 40 found.

Example

Input

7
50 30 70 20 40 60 80
3
40 65 50

Output

50 30 40 found
50 70 60 missing
50 found

Sample input available Sample output available

Editor

Java

Hints

Start at the root. Print each node you visit.

Smaller than the node → go left; bigger → go right; null → it's missing.

Solution explanation

The path length is at most the height of the tree. The second test shows a sorted insert order making a tall, list-like tree.

Show solution

import java.util.Scanner;

class Node {
    int value;
    Node left, right;
    Node(int value) { this.value = value; }
}

public class Main {
    static Node insert(Node node, int v) {
        if (node == null) return new Node(v);
        if (v < node.value) node.left = insert(node.left, v);
        else if (v > node.value) node.right = insert(node.right, v);
        return node;                       // duplicates are ignored
    }

    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int n = sc.nextInt();
        Node root = null;
        for (int i = 0; i < n; i++) root = insert(root, sc.nextInt());
        int q = sc.nextInt();
        StringBuilder sb = new StringBuilder();
        for (int i = 0; i < q; i++) {
            int x = sc.nextInt();
            Node cur = root;
            boolean found = false;
            while (cur != null) {
                sb.append(cur.value).append(' ');
                if (x == cur.value) { found = true; break; }
                cur = x < cur.value ? cur.left : cur.right;
            }
            sb.append(found ? "found" : "missing").append('\n');
        }
        System.out.print(sb);
    }
}

Output

Answer