Tree Builder

Problem #87

Tags: graphs data-structures

Who solved this?

3 2 5 4 8

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 single node 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. 2, 4 and 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 following:

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.

BUILDING PROCESS

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:

3 3 5 3 5 4 3 2 5 4 3 2 5 4 8

PROBLEM STATEMENT

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:

The tree from the picture above will be represented as:

((-,2,-),3,((-,4,-),5,(-,8,-)))

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.

Example:

input data:
5
3 5 4 2 8

output data:
((-,2,-),3,((-,4,-),5,(-,8,-)))
You need to login to get test data and submit solution.