# Binary Search Tree

Optional Node

The Tree data structure is used in many different areas of programming. For example, file systems use trees to store directories and files hierarchically. Another common usage of Trees is to sort data, such as in the Binary Search Tree.

### Data - Keys and Values

Many types of data consist of keys and values. For example, books (values) in libraries are stored based on their ISBN number (keys) and you can look up topics (keys) in a book index to find the page (value) that the topic is discussed.

Computers also use keys and values to help find information faster. As in the above examples, data is often associated with a key (usually a unique one), which can then be accessed to find the relevant data quickly. For example, a unique ID can be associated, with a book, song, user account, node, module and more. The data is then accessed by looking up the key in a data structure.

### Good Data Structure for Storing Data

Depending on the type of data involved, different data structures can be used that allow items to be stored, retrieved and deleted from the structure. The goal of the data structure is to allow these actions to be performed in an optimal manner.

Q: Why can't everything just be stored in unsorted Arrays?
A: Every time you want to retrieve an item, the computer will need to search through the whole array until it find the item.
Q: OK, so keep all the keys in the array sorted, and then find them quickly with Binary Search.
A: This would work if you have unchanging data that just needs to be set up once. However, a sorted array isn't a good choice if you need to add items too, since the whole arrays constantly needs to be shifted around. instead, we can use other structures, such as the Binary Search Tree.

• #### mike

static class Node{
Node left;
Node right;
int key;

``````    Node(int key){
this.key = key;
}
}

static void doStuff(int[] ar){
Node top = ar2SortedTree(ar);
``````