Trees - Searching in a binary search tree P92765


Statement
 

pdf   zip

thehtml

Write a program that reads a binary search tree with natural numbers, and that, for each read natural after that, indicates if it is or not in the tree, A binary tree is a search tree if, for each node, the elements of its left subtree are less than the element of the node, and the elements of its right subtree are greater than the element of the node.

Input

Input consists of the description of a tree as explained in problem P98436. For some historical reason, the number of internal nodes is also given just before, you may ignore it. You can assume that the given tree is a search tree. Then a sequence of natural numbers comes.

Output

For each natural given, your program must print a 1 if the natural is in the tree or a 0 if it is not.

Observation

This exercise could be solve ignoring the struct of the tree, e.g. by sorting the vector doing binary searches. The Judge could not detect this trick, but this would not serve you to practice the use of trees.

Public test cases
  • Input

    10
    180 155 60 -1 80 -1 -1 170 -1 -1 300
    240 -1 -1 400 310 -1 340 -1 -1 -1
    
    60
    180
    400
    310
    160
    0
    500
    

    Output

    60 1
    180 1
    400 1
    310 1
    160 0
    0 0
    500 0
    
  • Information
    Author
    Salvador Roura
    Language
    English
    Translator
    Carlos Molina
    Original language
    Catalan
    Other languages
    Catalan
    Official solutions
    C++ Python
    User solutions
    C++ Python