25MCS13 Data

Structure for Problem Solving

Module –1 8 :hrs
Elementary Data Structures: Data Structure Classification – Primitive and Non-Primitive,
Linear – Static-Array, Dynamic-Linked List, Stack, Queue, Non Linear – Tree, Graph.

Search Trees: Two Models of Search Trees. General Properties and Transformations. Height
of a Search Tree. Basic Find, Insert, and Delete. Returning from Leaf to Root. Dealing with
Non unique Keys. Queries for the Keys in an Interval. Building Optimal Search Trees.
Converting Trees into Lists. Removing a Tree.

1. Elementary Data Structures: Data Structure

Classification – Primitive and Non-Primitive

DATA STRUCTURE

 Data structure is a representation of the logical relationships existing between

individual elements of data.
 A data structure is a way of organizing all data items that considers not only
the elements stored but also their relationship to each other.
 The logical or mathematical model of a particular organization of data is
called a data structure.

CLASSIFICATION OF DATA STRUCTURES

Data Structures can be divided into two categories,
i) Primitive Data Structures

1
 25MCS13 Data
Structure for Problem Solving

ii) ii) Non-Primitive Data Structures

Primitive Data Structures These are basic data structures and are directly operated upon by
the machine instructions. These data types consists of characters that cannot be divided and
hence they also called simple data types. Example: Integers, Floating Point Numbers,
Characters and Pointers etc.

Non-Primitive Data Structures These are derived from the primitive data structures. The
non-primitive data structures emphasizeon structuring of a group of homogeneous or
heterogeneous data items. Example: Arrays, Lists and Files, Graphs, trees etc. Based on the
structure and arrangement of data, non-primitive data structures is further classified into

1. Linear Data Structure

2. Non-linear Data Structure

1. Linear Data Structure: A data structure is said to be linear if its elements form a sequence
or a linear list. There are basically two ways of representing such linear structure in memory.

1. One way is to have the linear relationships between the elements represented by means of
sequential memory location. These linear structures are called arrays.

2
 25MCS13 Data
Structure for Problem Solving

2. The other way is to have the linear relationship between the elements represented by means
of pointers or links. These linear structures are called linked lists. The common examples of
linear data structure are Arrays, Queues, Stacks, Linked lists

2. Non-linear Data Structure: A data structure is said to be non-linear if the data are not
arranged in sequence or a linear. The insertion and deletion of data is not possible in linear
fashion. This structure is mainly used to represent data containing a hierarchical relationship
between elements. Trees and graphs are the examples of non-linear data structure.

2. Linear – Static-Array
An array is a data structure that stores a collection of elements of the same data type
in contiguous memory locations

Linear Array:
A linear array is a data structure that stores a collection of elements of the same data
type in contiguous memory locations. The elements are arranged sequentially,
forming a linear list. Each element can be accessed directly using an index, which
represents its position within the array. This direct access is a key characteristic,
allowing for efficient retrieval and manipulation of data based on its index.

Static Array:
A static array is a type of array where the size is fixed and determined at compile-time
or when the array is declared. Once a static array is created, its capacity cannot be
changed during the program's execution. This means that if you declare an array to
hold 10 elements, it will always hold space for 10 elements, regardless of whether you
actually store that many.

3. Dynamic-Linked List

3
 25MCS13 Data
Structure for Problem Solving

A dynamic linked list is a fundamental data structure concept in computer science. Its
"dynamic" nature refers to its ability to grow and shrink in size during program
execution (runtime), as opposed to static data structures like arrays, which have a
fixed size defined at compile time. This flexibility is achieved by allocating and
deallocating memory for individual nodes as needed, typically from the heap, and
connecting these nodes using pointers.

Key characteristics and types of dynamic linked lists:

 Nodes and Pointers:
A linked list is composed of individual units called nodes. Each node contains data
and a pointer (or reference) to the next node in the sequence.
 Dynamic Memory Allocation:
Nodes are allocated dynamically, meaning memory is requested from the system only
when a new element needs to be added, and released when an element is removed.

4. Stack
 The stack is the simplest of all structures, with an obvious interpretation:
putting objects on the stack and taking them off again, with access possible
only to the top item.
 For this reason they are sometimes also described as LIFO storage: last in, first
out. Stacks occur in programming wherever we have nested blocks, local
variables, recursive definitions, or backtracking. Typical programming
exercises that involve a stack are the evaluation of arithmetic expressions with
parentheses and operator priorities, or search in a labyrinth with backtracking.
 The stack should support at least the following operations:

{push( obj ): Put obj on the stack, making it the top item.
{ pop(): Return the top object from the stack and remove it from the stack.
{ stack empty(): Test whether the stack is empty

4
 25MCS13 Data
Structure for Problem Solving

 Also, the realization of the stack has, of course, to give the right
values, so we need to specify the correct behavior of a stack. One
method would be an algebraic specification of what correct sequences
of operations and return values are.
 This has been done for simple structures like the stack, but even then
the specification is not very helpful in understanding the structure.
Instead, we can describe a canonical implementation on an idealized
machine, which gives the correct answer for all correct sequences of
operations (no pop on an empty stack, no memory problems caused by
bounded arrays).
 Assuming that the elements we want to store on the stack are of type
item t, this could look as follows:

This describes the correct working of the stack, but we have the problem of assuming
both an infinite array and that any sequence of operations will be correct. A more
realistic version might be the following:

5
 25MCS13 Data
Structure for Problem Solving

 This now limits the correct behavior of the stack by limiting the maximum
number of items on the stack at one time, so it is not really the correct stack
we want, but at least it does specify an error message in the return value if the
stack overflow is reached by one push too many.
 This is a fundamental defect of array-based realizations of data structures: they
are of fixed size, the size needs to be decided in advance, and the structure
needs the full size no matter how many items are really in the structure.
 There is a systematic way to overcome these problems for array-based
structures, which we will see in Section 1.5, but usually a solution with
dynamically allocated memory is preferable.
 We specified an error value only for the stack overflow condition, but not for
the stack underflow, because the stack overflow is an error generated by the
structure, which would not be present in an ideal implementation, whereas a
stack underflow is an error in the use of the structure and so a result in the
program that uses the stack as a black box.
 Also, this allows us to keep the return value of pop as the top object from the
stack; if we wanted to catch stack underflow errors in the stack
implementation, we would need to return the object and the error status.
 A final consideration in our first stack version is that we might need multiple
stacks in the same program, so we want to create the stacks dynamically. For

6
 25MCS13 Data
Structure for Problem Solving

this we need additional operations to create and remove a stack, and each stack
operation needs to specify which stack it operates on. One possible
implementation could be the following:

7
 25MCS13 Data
Structure for Problem Solving

 Notice that we have a placeholder node in front of the linked list; even an empty stack
is represented by a list with one node, and the top of the stack is only the second node
of the list.
 This is necessary as the stack identifier returned by create stack and used in all stack
operations should not be changed by the stack operations. So we cannot just use a
pointer to the start of the linked list as a stack identifier.
 Because the components of a node will be invalid after it is returned, we need
temporary copies of the necessary values in pop and remove stack. The operation
remove stack should return all the remaining nodes; there is no reason to assume that
only empty stacks will be removed, and we will suffer a memory leak if we fail to
return the remaining nodes.

8
 25MCS13 Data
Structure for Problem Solving

OPERATIONS PERFORMED ON STACK

The primitive operations performed on the stack are as follows:

PUSH: The process of adding (or inserting) a new element to the top of the stack is
called PUSH operation. Pushing an element to a stack will add the new element at the
top. After every push operation the top is incremented by one. If the array is full and
no new element can be accommodated, then the stack overflow condition occurs.
POP: The process of deleting (or removing) an element from the top of stack is called
POP operation. After every pop operation the stack is decremented by one. If there is
no element in the stack and the pop operation is performed then the stack underflow
condition occurs.

9
 25MCS13 Data
Structure for Problem Solving

5. Queue
The queue is a structure almost as simple as the stack; it also stores items, but it
differs from the stack in that it returns those items first that have been entered first, so
it is FIFO storage (first in, first out). Queues are useful if there are tasks that have to
be processed cyclically. Also, they are a central structure in breadth-first search;
breadth-first search (BFS) and depth-first search (DFS) really differ only in that BFS
uses a queue and DFS uses a stack to store the node that will be explored next.

The queue should support at least the following operations:

{ enqueue( obj ): Insert obj at the end of the queue, making it the last item.
{ dequeue(): Return the first object from the queue and remove it from the queue.
{ queue empty(): Test whether the queue is empty.

Again we assume, as in all dynamically allocated structures, that the operations get
node and return node are available, which always work correctly and in constant time.
Because we want to remove items from the front of the queue, the pointers in the
linked list are oriented from the front to the end, where we insert items. There are two
aesthetical disadvantages of this obvious implementation: we need a special entry
point structure, which is different from the list nodes, and we always need to treat the
operations involving an empty queue differently. For insertions into an empty queue
and removal of the last element of the queue, we need to change both insertion and
removal pointers; for all other operations we change only one of them.

10
 25MCS13 Data
Structure for Problem Solving

Or one could implement the queue as a doubly linked list, which requires no case
distinctions at all but needs two pointers per node. Minimizing the number of pointers
is an aesthetic criterion more justified by the amount of work that has to be done in
each step to keep the structure consistent than by the amount of memory necessary for
the structure. Here is a doubly linked list implementation:

11
 25MCS13 Data
Structure for Problem Solving

12
 25MCS13 Data
Structure for Problem Solving

13
 25MCS13 Data
Structure for Problem Solving

14
 25MCS13 Data
Structure for Problem Solving

6. Non Linear – Tree

Tree is a non-linear data structure which organizes data in hierarchical fashion and
the tree structure follows
a recursive pattern of organizing and storing data.
Every individual element is called as Node. Node in a tree data structure, stores the
actual data of that
particular element and link to next element in hierarchical structure.
if there are N number of nodes in a tree structure, then there can be a maximum of N-
1 number of links.

1. Root
In a tree data structure, the first node is called as Root Node. Every tree must have
root node. We can say that
root node is the origin of tree data structure. In any tree, there must be only one root
node. We never have

15
 25MCS13 Data
Structure for Problem Solving

multiple root nodes in a tree. Ex: ‘A’ in the above tree

2. Edge
In a tree data structure, the connecting link between any two nodes is called as EDGE.
In a tree with 'N'
number of nodes there will be a maximum of 'N-1' number of edges. Ex: Line
between two nodes.

3. Parent
In a tree data structure, the node which is predecessor of any node is called as
PARENT NODE. In simple
words, the node which has branch from it to any other node is called as parent node.
Parent node can also be
defined as "The node which has child / children".
Ex: A,B,C,E & G are parent nodes

4. Child
In a tree data structure, the node which is descendant of any node is called as CHILD
Node. In simple words,
the node which has a link from its parent node is called as child node. In a tree, any
parent node can have any
number of child nodes. In a tree, all the nodes except root are child [Link]: B & C
are children of A, G &
H are children of C and K child of G

5. Siblings
In a tree data structure, nodes which belong to same Parent are called as SIBLINGS.
In simple words, the
nodes with same parent are called as Sibling [Link]: B & C are siblings, D, E and F
are siblings, G & H
are siblings, I & J are siblings

16
 25MCS13 Data
Structure for Problem Solving

6. Leaf
In a tree data structure, the node which does not have a child is called as LEAF Node.
In simple words, a leaf
is a node with no child. In a tree data structure, the leaf nodes are also called as
External Nodes. External
node is also a node with no child. In a tree, leaf node is also called as 'Terminal'
[Link]: D,I,J,F,K AND
Hare leaf nodes

7. Internal Nodes
In a tree data structure, the node which has atleast one child is called as INTERNAL
Node. In simple words,
an internal node is a node with atleast one child.
In a tree data structure, nodes other than leaf nodes are called as Internal Nodes. The
root node is also said to
be Internal Node if the tree has more than one node. Internal nodes are also called as
'Non-Terminal' nodes.
Ex: A,B,C,E & G

8. Degree of a node
In a tree data structure, the total number of children of a node is called as DEGREE of
that Node. In simple
words, the Degree of a node is total number of children it has. The highest degree of a
node among all the
nodes in a tree is called as 'Degree of Tree'.Ex: Degree of B is 3, A is 2 and of F is 0

9. Level of a node
In a tree data structure, the root node is said to be at Level 0 and the children of root
node are at Level 1 and
the children of the nodes which are at Level 1 will be at Level 2 and so on... In simple
words, in a tree each
step from top to bottom is called as a Level and the Level count starts with '0' and
incremented by one at each

17
 25MCS13 Data
Structure for Problem Solving

level (Step).

18
 25MCS13 Data
Structure for Problem Solving

19
 25MCS13 Data
Structure for Problem Solving

7. Graph

Definitions: Graph, Vertices, Edges

 Define a graph G = (V, E) by defining a pair of sets:
1. V = a set of vertices
2. E = a set of edges
 Edges:
o Each edge is defined by a pair of vertices
o An edge connects the vertices that define it
 Vertices:
o Vertices also called nodes
o Denote vertices with labels
Representation:
o Represent vertices with circles, perhaps containing a label
o Represent edges with lines between circles
Example:
o V = {A,B,C,D}

20
 25MCS13 Data
Structure for Problem Solving

o E = {(A,B),(A,C),(A,D),(B,D),(C,D)}

Many algorithms use a graph representation to represent data or the or the problem to be

Solved

 Examples of Graph applications:

o Cities with distances between

o Roads with distances between intersection points

o Course prerequisites

o Network and shortest routes

o Social networks

o Electric circuits, projects planning and many more...

21
 25MCS13 Data
Structure for Problem Solving

Undirected Graphs

22
 25MCS13 Data
Structure for Problem Solving

23
 25MCS13 Data
Structure for Problem Solving

24
 25MCS13 Data
Structure for Problem Solving

8. Search Trees: Two Models of Search Trees.

The two models of search trees are as follows:

1. Take left branch if query key is smaller than node key; otherwise take the right
branch, until you reach a leaf of the tree. The keys in the interior node of the tree are
only for comparison; all the objects are in the leaves.
2. Take left branch if query key is smaller than node key; take the right branch if the
query key is larger than the node key; and take the object contained in the node if they
are equal.

This minor point has a number of consequences:

25
 25MCS13 Data
Structure for Problem Solving

 { In model 1, the underlying tree is a binary tree, whereas in model 2, each tree node
is really a ternary node with a special middle neighbor.
 { In model 1, each interior node has a left and a right subtree (each possibly a leaf
node of the tree), whereas in model 2, we have to allow incomplete nodes, where left
or right subtree might be missing, and only the comparison object and key are
guaranteed to exist.

 So the structure of a search tree of model 1 is more regular than that of a tree of model
2; this is, at least for the implementation, a clear advantage.
 { In model 1, traversing an interior node requires only one comparison, whereas in
model 2, we need two comparisons to check the three possibilities.

 Indeed, trees of the same height in models 1 and 2 contain at most approximately the
same number of objects, but one needs twice as many comparisons in model 2 to
reach the deepest objects of the tree. Of course, in model 2, there are also some
objects that are reached much earlier; the object in the root is found with only two
comparisons, but almost all objects are on or near the deepest level.

Theorem. A tree of height h and model 1 contains at most 2h objects. A tree of height
h and model 2 contains at most 2h+1 − 1 objects.

 This is easily seen because the tree of height h has as left and right subtrees a tree of
height at most h − 1 each, and in model 2 one additional object between them.

 { In model 1, keys in interior nodes serve only for comparisons and may reappear in
the leaves for the identification of the objects. In model 2, each key appears only
once, together with its object.

26
 25MCS13 Data
Structure for Problem Solving

27
 25MCS13 Data
Structure for Problem Solving

9. General Properties and Transformations

 In a correct search tree, we can associate each tree node with an interval, the
interval of possible key values that can be reached through this node.
 The interval of root is ]–∞,∞[, and if *n is an interior node associated with
interval [a, b[, then n->key ∈ [a, b[, and n->left and n->right have as
associated intervals [a, n->key[ and [n->key, b[. With the exception of the
intervals starting in −∞, all these intervals are half-open, containing the left
endpoint but not the right endpoint.
 This implicit structure on the tree nodes is very helpful in understanding the
operations on the trees.

28
 25MCS13 Data
Structure for Problem Solving

 The same set of (key, object) pairs can be organized in many distinct correct
search trees: the leaves are always the same, containing the (key, object) pairs
in increasing order of the keys, but the tree connecting the leaves can be very
different, and we will see that some trees are better than others.
 There are two operations – the left and right rotations – that transform a
correct search tree in a different correct search tree for the same set. They are
used as building blocks of more complex tree transformations because they are
easy to implement and universal.
 Suppose *n is an interior node of the tree and n->right is also an interior node.
Then the three nodes n->left, n->right->left, and n->right->right have
consecutive associated intervals whose union is the associated interval of *n.
 Now instead of grouping the second and third intervals (of n->right->left and
n->right->right) together in node n->right, and then this union together with
the interval of n->left in *n, we could group the first two intervals together in
a new node, and that then together with the last interval in *n.
 This is what the left rotation does: it rearranges three nodes below a given
node *n, the rotation center. This is a local change done in constant time; it
does not affect either the content of those three nodes or anything below them
or above the rotation center *n. The following code does a left rotation around
*n:

29
 25MCS13 Data
Structure for Problem Solving

30
 25MCS13 Data
Structure for Problem Solving

31
 25MCS13 Data
Structure for Problem Solving

[Link] of a Search Tree.

 The central property which distinguishes the different combinatorial types of
search trees for the same underlying set and which makes some search trees
good and others bad is the height.
 The height of a search tree is the maximum length of a path from the root to a
leaf – the maximum taken over all leaves. Usually not all leaves are at the
same distance from the root; the distance of a specific tree node from the root
is called the depth of that node.
 the maximum number of leaves of a search tree of height h is 2h. And at the
other end, the minimum number of leaves is h + 1 because a tree of height h
must have at least one interior node at each depth 0,...,h − 1, and a tree with h
interior nodes has h + 1 leaves. Together, this gives the bounds.

32
 25MCS13 Data
Structure for Problem Solving

[Link] Find, Insert, and Delete.

The search tree represents a set of (key, object) pairs, so it must allow some
operations with this set. The most important operations that any search tree needs to
support are as follows:

33
 25MCS13 Data
Structure for Problem Solving

 We will now describe here the basic find, insert, and delete operations on the
search trees, The simplest operation is the find: one just follows the associated
interval structure to the leaf, which is the only place that could hold the right
object.
 Then one tests whether the key of this only possible candidate agrees with the
query key, in which case we found the object, or not, in which case there is no
object for that key in the tree.

34
 25MCS13 Data
Structure for Problem Solving

35
 25MCS13 Data
Structure for Problem Solving

36
 25MCS13 Data
Structure for Problem Solving

37
 25MCS13 Data
Structure for Problem Solving

 The delete operation is even more complicated because when we are deleting a
leaf, we must also delete an interior node above the leaf.
 For this, we need to keep track of the current node and its upper neighbor
while going down in the tree.
 Also, this operation can lead to an error if there is no object with the given
key.

38
 25MCS13 Data
Structure for Problem Solving

 If there is additional information in the nodes, it must also be copied or

updated when we copy the content of the other node into the upper
node. Note that we delete the nodes, but not the object itself.
 There might be other references to this object. But if this is the only
reference to the object, this will cause a memory leak, so we should
delete the object. This is the responsibility of the user, so we return a
pointer to the object.

12. Returning from Leaf to Root

 Any tree operation starts at the root and then follows the path down to the leaf where
the relevant object is or where some change is performed.
 we need to return along this path, from the leaf to the root, to perform some update or
rebalancing operations on the nodes of this path. And these operations need to be done
in that order, with the leaf first and the root last.

39
 25MCS13 Data
Structure for Problem Solving

 But without additional measures, the basic search-tree structure we described does
not contain any way to reconstruct this sequence. There are several possibilities to
save this information.

1. A stack: If we push pointers to all traversed nodes on a stack during descent to the leaf,
then we can take the nodes from the stack in the correct (reversed) sequence afterward. This
is the cleanest solution under the criterion of information economy; it does not put any
additional information into the tree structure. Also, the maximum size of the stack needed is
the height of the tree, and so for the balanced search trees, it is logarithmic in the size of the
search tree. An array-based stack for 200 items is really enough for all realistic applications
because we will never have 2100 items. This is also the solution implicitly used in any
recursive implementation of the search trees.

2. Back pointers: If each node contains not only the pointers to the left and right subtrees, but
also a pointer to the node above it, then we have a path up from any node back to the root.
This requires an additional field in each node. As additional memory requirement, this is
usually no problem because memory is now large. But this pointer also has to be corrected in
each operation, which makes it again a source of possible programming errors.

3. Back pointer with lazy update: If we have in each node an entry for the pointer to the node
above it, but we actually enter the correct value only during descent in the tree, then we have
a correct path from the leaf we just reached to the root. We do not need to correct the back
pointers during all operations on the tree, but then the back pointer field can only be assumed
to be correct for the nodes on the path along which we just reached the leaf.

Any of these methods will do and can be combined with any of the balancing techniques.
Another method that requires more care in its combination with various balancing techniques
is the following:

4. Reversing the path: We can keep back pointers for the path even without an extra entry for
a back pointer in each node by reversing the forward pointers as we go down the tree. While
going down in each node, if we go left, the left pointer is used as back pointer and if we go
right, the right pointer is used as back pointer. When we go up again, the correct forward
pointers must be restored.

40
 25MCS13 Data
Structure for Problem Solving

13. Dealing with Non unique Keys.

 In practical applications, it is not uncommon that there are several objects with the
same key. In database applications, we might have to store many objects with the
same key value; there it is a quite unrealistic assumption that each object is uniquely
identified by each of its attribute values, but there are queries to list all objects with a
given attribute value. So any realistic search tree has to deal with this situation.
 The correct reaction is as follows:

 The obvious way to realize this behavior is to keep all elements of the same key in a
linked list below the corresponding leaf of the search tree. Then find just produces all
elements of that list; insert always inserts at the beginning of the list; only delete in
time independent of the number of deleted items requires additional information.
 For this, we need an additional node between the leaf and the linked list, which
contains pointers to the beginning and to the end of the list; then we can transfer the
entire list with O(1) operations to the free list of our dynamic memory allocation
structure. Again, this way we only delete the references to the objects contained in this
tree.
 If we need to delete the objects themselves, we can do it by walking along this list,
but not in O(1) time independent of the number of objects.

14. Queries for the Keys in an Interval

 Up to now we have discussed only the query operation find, which, for a given key,
retrieves the associated object.
 Frequently, a more general type of query is useful, in which we give a key interval [a,
b[ and want to find all keys that are contained in this interval. If the keys are subject
to small errors, we might not know the key exactly, so we want the nearest key value
or the next larger or next smaller key.

41
 25MCS13 Data
Structure for Problem Solving

 Without such an extension, our find operation just answers that there is no object with
the given key in the current set, which is correct but not helpful. There are other types
of dictionary structures on hash tables that cannot support this type of query. But for
search trees, it is a very minor modification, which can be done in several ways.
 1. We can organize the leaves into a doubly linked list and then we can move in O(1)
time from a leaf to the next larger and the next smaller leaf. This requires a change in
the insertion and deletion functions to maintain the list, but it is an easy change that
takes only O(1) additional time. The query method is also almost the same; it takes
O(k) additional time if it lists a total of k keys in the interval.
 2. An alternative method does not change the tree structure at all but changes the
query function: we go down the tree with the query interval instead of the query key.
Then we go left if [a, b[< node->key; right if node->key ≤ [a, b[; and sometimes we
have to go both left and right if a < node->key ≤ b. We store all those branches that
we still need to explore on a stack. The nodes we visit this way are the nodes on the
search path for the beginning of the query interval a, the search path for its end b, and
all nodes that are in the tree between these paths. If there are i interior nodes between
these paths, there must be at least i + 1 leaves between these paths. So if this method
lists k leaves, the total number of nodes visited is at most twice the number of nodes
visited in a normal find operation plus O(k). Thus, this method is slightly slower than
the first method but requires no change in the insert and delete operations.
 Next we give code for the stack-based implementation of interval find. To illustrate
the principle, we write here just the generic stack operations; these need, of course, to
be filled in. The output of the operation is potentially long, so we need to return many
objects instead of a single result. For this, we create a linked list of the (key, object)
pairs found in the query interval, which is linked here by the right pointers. After use
of the results, the nodes of this list need to be returned to avoid a memory leak.

42
 25MCS13 Data
Structure for Problem Solving

15. Building Optimal Search Trees.

 Occasionally it is useful to construct an optimal search tree from a given set of (key,
object) pairs. This can be viewed as taking search trees as static data structure: there
are no inserts and deletes, so there is no problem of rebalancing the tree, but if we
build it, knowing the data in advance, then we should build it as good as possible.
 The primary criterion is the height; because a search tree of height h has at most 2h
leaves, an optimal search tree for a set of n items has height log n, where the log, as
always, is taken to base 2.

43
 25MCS13 Data
Structure for Problem Solving

 We assume that the (key, object) pairs are given in a sorted list, ordered with
increasing keys. There are two natural ways to construct a search tree of optimal
height from a sorted list: bottom-up and top-down.
 The bottom-up construction is easier: one views the initial list as list of one-element
trees. Then one goes repeatedly through the list, joining two consecutive trees, until
there is only one tree left.
 This requires only a bit of bookkeeping to insert the correct comparison key in each
interior node. The disadvantage of this method is that the resulting tree, although of
optimal height, might be quite unbalanced: if we start with a set of n = 2m + 1 items,
then the root of the tree has on one side a subtree of 2m items and on the other side a
subtree of 1 item.
 Next is the code for the bottom-up construction. We assume here that the list items are
themselves of type tree node t, with the left entry pointing to the object, the key
containing the object key, and the right entry pointing to the next item, or NULL at
the end of the list.
 We first create a list, where all the nodes of the previous list are attached as leaves,
and then maintain a list of trees, where the key value in the list is the smallest key
value in the tree below it.

44
 25MCS13 Data
Structure for Problem Solving

45
 25MCS13 Data
Structure for Problem Solving

46
 25MCS13 Data
Structure for Problem Solving

47
 25MCS13 Data
Structure for Problem Solving

48
 25MCS13 Data
Structure for Problem Solving

49
 25MCS13 Data
Structure for Problem Solving

50
 25MCS13 Data
Structure for Problem Solving

16. Converting Trees into Lists

 Occasionally one also needs the other direction, converting a tree into an ordered list.
This is very simple, using a stack for a trivial depth-first search enumeration of the
leaves in decreasing order, which we insert in front of the list.
 This converts in O(n) time a search tree with n leaves into a list of n elements in
increasing order. Again we write the generic stack functions, which in the specific
implementation should be replaced by the correct method.
 If one knows in advance that the height of the tree is not too large, an array is the
preferred method; the size of the array needs to be at least as large as the height of the
tree.

51
 25MCS13 Data
Structure for Problem Solving

17. Removing a Tree.

 We also need to provide a method to remove the tree when we no longer need it. As
we already remarked for the stacks, it is important to free all nodes in such a
dynamically allocated structure correctly, so that we avoid a memory leak.
 We cannot expect to remove a structure of potentially large size in constant time, but
time linear in the size of the structure, that is, constant time per returned node, is
easily reached. An obvious way to do this is using a stack, analogous to the previous
method to covert a tree into a sorted list. A more elegant method is the following:

52
 25MCS13 Data
Structure for Problem Solving

 This essentially performs rotations in the root till the left-lower neighbor is a leaf;
then it returns that leaf, moves the root down to the right, and returns the previous
root.

53