You give, one by one, a list of distinct integers, from 1 to n
, in any order. Each integer
is added to the binary search tree using the classical definition of how to add a number to a
binary search tree:
- If the tree has no root, a root r is added to the tree, with empty left and right
subtrees, and is attached to the value v(r) = k;
- Otherwise, the integer is recursively added to the left subtree of r if v(r) <
k, and to the right subtree if v(r) > k.
Due to this definition, each new node is always a new leaf of the tree.
The tree is initially empty.
Graphical representation of the tree
The tree, the bombs and the goals are drawn on a grid with integer coordinates.
Each time an integer is added to the tree, the drawing is updated using the following rules.
The tree is drawn in a rectangle with a given odd width
and a given height
coordinates vary between (0, 0)
and (width - 1, height - 1)
. The root of the
tree is always placed at coordinates ((width - 1)/ 2, 0)
. The left child (respectively the
right child) of a node with coordinates (x, y)
is placed at coordinates (x - 1, y + 1)
(respectively (x + 1, y + 1)
On the graphical interface of the game, the root is drawn in blue, some coordinates are unreachable (for
instance the coordinate (0, 0)
and are drawn in gray.
- by adding an integer to the tree, it is placed out of the bounds (the x-coordinate should be between 0 and
width-1, and the y-coordinate should be between 0 and height - 1;
- by adding an integer to the tree, it is placed on a bomb;
- after adding all the integers to the tree, a goal is not reached;
- by adding an integer to the tree, it is placed at the same coordinates than another integer;
- you do not supply an integer between 1 and n;
- you supply the same integer twice;
- you do not supply a valid integer in time.
when all the goals are reached. It is allowed to place only a part of the
integers between 1 and n.