Challenge: Is It in the Tree?

Lab Python Beginner 10 points

Build a BST from the first line. Then for each number on the second line, print found or missing, followed by how many nodes were checked.

Input

Line 1: whole numbers to insert. Line 2: numbers to search for.

Output

One line per search: found <steps> or missing <steps>.

Example

Input

8 3 10 1 6 14
6 7 8 15

Output

found 3
missing 3
found 1
missing 3

Sample input available Sample output available

Editor

Python

Hints

Count a step for each node you look at.

Go left when the target is smaller, right when bigger, stop at None.

Solution explanation

The number of steps is at most the height of the tree.

Show solution

class Node:
    def __init__(self, value):
        self.value = value
        self.left = None
        self.right = None


def insert(root, value):
    if root is None:
        return Node(value)
    if value < root.value:
        root.left = insert(root.left, value)
    elif value > root.value:
        root.right = insert(root.right, value)
    return root


values = list(map(int, input().split()))
root = None
for v in values:
    root = insert(root, v)

for t in map(int, input().split()):
    node, steps = root, 0
    while node:
        steps += 1
        if t == node.value:
            break
        node = node.left if t < node.value else node.right
    print("found" if node else "missing", steps)

Output

Answer