**ICOM 4035 – Data Structures**

**Fall 2007**

**Laboratory 7: Trees and Binary Search
Trees**

**1.
****Objectives**

- Introduce the tree as a data structure.
- Compare trees to lists, stacks and queues.
- Practice operations on trees.

**2.
****Overview**

Just until now you have seen several data structures and their characteristics. Among these the linked list, the stack and the queue. As seen the linked list allows dynamic expansion of the storage size easily in contrast to an array list which is implemented using dynamic arrays. However the linked list had the issue of access, due to the fact that one only has access to the first element of the list and some times the last and in order to get the element in the middle one had to run the list until finding it.

The other two data structures, the stack and the queue, were similar to the linked list but didn’t allow extracting the element from the middle of the list. Again these were useful for applications with special behaviors.

As an alternative to solve these issues of accessing elements
faster than a linked list can but without loosing the ability to add new
elements in an efficient way comes the use of **Trees**. This data structure uses hierarchical organization to access
data.

Example of a Tree

The first node is known as the **root** of the tree and it has pointer references to other nodes known
as **descendants**. Locally each node
can be seen as the root or **parent** of
a sub-tree. At the end there will be some nodes without any **children**, these are referred as **leaves**. A tree also has its **height** which is the maximum number of connections
from a leaf up to the root.

There is a special type of tree called the BinarySearchTree which has all nodes sorted according to a specific key value. In this type of tree we have that a parent node can have at most two children, the one at the left having a key value smaller than the parent and the one at the right having a key value larger than the parent.

**3.
****Practice**

Download lab7.tar.gz and implement the missing methods inside of LinkedBinaryTree.java (addRoot(), insertLeft(), insertRight() and remove()). Then finish the recursive method HelloPrint inside of lab7.java. Implement this method in a way that the output is “Hello World!”. Note that is kind like the pre-order iteration but with minor details.

Hint: Draw the LinkedBinaryTree