If you know what Tree is, how search in it and building from sequence of values are performed - then feel free to jump to Problem Statement directly.
Tree is a data structure very popular in programming. Just imagine - each web-site usually have some database, each database is usually built of tables, each table usually have one or more indexes - and these indexes are usually implemented as trees.
There are many types of trees - binary and non-binary, with many algorithms of self-balancing etc. However we'll start with one of the simplest forms.
Let us agree that tree consists of nodes, and each node contains:
The branches of the node could be either empty or linked to some node (one branch to one node). No loops of links may exist and so there is always some root node.
Look at the picture above: here the node marked with
3 is the root. Its left branch have a subtree consisting of a
2, and node
2 has both its branches empty. Right branch of
3 leads to node
5 which have both
branches leading to two more nodes.
Nodes without branches are sometimes called leaves (i.e.
8 in our example). Some tree architectures
do not store values in the nodes other than leaves. Though it is not our case.
SEARCH IN A TREE
Note that our sample tree have a nice property - all left children of the given node contain smaller values, while all
right children contain greater values. So if we want to find out whether the tree contains value
4 we can do the
3which is less than we want, so go to the right branch;
5- it is now greater than the value we look for, so go to its left branch;
4- that is what we wanted!
In case if we seek for value
6 we will end at the node
8 from which we want to go to the left, but it have its
left branch empty - so we conclude there is no such value in the tree at all.
So our tree is binary (because each node have no more than two children) and it has ordering allowing us to find values without checking the whole tree.
Suppose we have an array of values, like this
(3, 5, 4, 2, 8) and we want to build a tree from it to simplify search
as explained above. The building algorithm looks quite similar to search - we need to "search" for element and when
we find the place where it should be, but there is an empty branch - we just insert new node here:
5we check the root and since
3is less, we go to right - this branch is empty, so create new node here with
5as a value;
4we go from
3to right, then from
5to left - and this left branch is empty, so hang new node with
2should go to the left of
3, there was nothing before so create node with
2as left branch of
8goes to the right of
3and to the right of
5and makes new node there.
You are to create binary ordered tree from sequence of numbers as explained above (without caring of rebalancing it). For each next number simply find the place where it should be inserted and add it there.
To represent the output, use the following format:
valueis always a number;
rightcould be empty, which is specified with dash
The tree from the picture above will be represented as:
Input data will contain the length of array which should be converted to tree.
The next line will contain the array itself - integers, separated by spaces.
Answer should contain the tree description in the format specified above.
input data: 5 3 5 4 2 8 output data: ((-,2,-),3,((-,4,-),5,(-,8,-)))