2
$\begingroup$

I'm trying to solve the following question:

The keys $1,2,\ldots,17$ are stored in a search tree. In the current situation, the root of the search tree has exactly 2 children. From the right side of the root begins a simple route to the leaf that begins with a sequence of 4 edges from the left white parent, and ends with a sequence of 3 edges from the right parent. From the left son of the root begins a simple path to the leaf that begins with a sequence of 4 edges from the right white parent, and ends with a sequence of 3 edges from the left parent white. Draw the tree.

Now, I understand how the structure looks like:

enter image description here

But I can't seem to figure out how the keys should look like in the graph. If it's a search tree, then there could be only one way to create this tree? If so, how the mapping function should look like?

In the solution, they draw it like so:

enter image description here

Can you please explain which algorithm/method they followed to fill the graph with the right keys? How would I solve this question if another structure was given?

$\endgroup$

1 Answer 1

1
$\begingroup$

There are in fact different kinds of search tree. Presumably you have only encountered one type so far, which is why you are somehow expected to understand how the tree works without being told what kind of tree it is.

Specifically, you are working with a binary search tree. Starting at any node $N$ with key $k$ in this tree, the key of the left child (if there is one) and all keys that are reachable through the left child are less than $k$, and the key of the right child (if there is one) and all keys that are reachable through the right child are greater than $k$.

Starting at the top node, by counting the nodes reachable through the left branch we see that there must be eight keys less than the key of the top node, and by counting the nodes reachable through the right branch we see that there must be eight keys greater than the key of the top node. Out of all the numbers $1, 2, 3, \ldots, 17$, which one has eight keys smaller than it and eight keys larger? It can only be $9$. That's the number to write in the top node.

Now looking at the left child of the top node, we know it and all nodes below it have keys less than $9$; they must be $1, 2, 3, \ldots, 8.$ But since this new node has only a right child, all the keys in the chain below it must be greater than its key. That is, this node has the smallest of all those numbers; therefore its key is $1.$

Just continue like that to fill in the rest of the diagram.

$\endgroup$

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .