# Trees

## Goals

- Understand tree data structures.
- Implement and use a binary search tree.

## Concepts

- balanced binary tree
- binary search tree (BST)
- binary tree
- branch
- breadth-first traversal
- child node
- depth-first traversal
- in-order traversal
- leaf node
- parent node
- post-order traversal
- pre-order traversal
- root node
- subtree
- tree

### Library

## Lesson

A tree is directed graph in which each vertex (usually referred to just as a “node”) has at most one edge coming in, and may have any number of edges going out; to vertices that are not shared with other vertices. A traditional file system is a well-known example of a tree, in which each directory can itself contain files and subdirectories, and so on. A Java class hierarchy is also a tree, as you can see in the `Vehicle`

class diagram from a previous lesson.

A tree has certain features that are given names:

- The vertices from the edges going out of a vertex are called child nodes.
- The vertex from the edge coming into a vertex is called the parent node.
- Each node in a tree makes up a subtree.
- An edge and its subtree is called a branch.
- The root node is the ultimate parent of all nodes in a tree.
- The nodes without any children (those on the opposite end of the tree from the root) are called leaf nodes.

### Binary Tree

As you might have guessed from the terms above, a tree is a good data structure for representing the relationship among objects. A tree can hold objects in a sorted order. A simple-to-understand example of such a tree is a binary tree, in which each node has potentially two children—hence the use of the term “binary”. The two child nodes are called the “left” and “right” nodes, for obvious reasons. Here is an example binary tree node holding `java.util.Long`

instances:

You can use a binary tree to hold sorted numbers. For each node, use the subtree tree on the left to hold numbers *less than* the number held by the node itself, and use the tree on the right would hold numbers *greater than* the node itself, as in the diagram.

This sort of tree makes it easy to search for items. Instead of searching through every single value, if the value held by a particular node does not match one needs either to search the left subtree or the right subtree, based upon whether the object being searched for is less than or greater than the object held by the node. You should see that this sort of binary tree represents the pattern of searching that would occur in the binary search algorithm you already learned. Not coincidentally this type of binary tree is called a binary search tree (BST).

### Tree Traversal

For a student leaving school on foot, there may be several ways to get home. They will cross the same streets on the way, but they will cross them in a different order depending on which corner they turn. Similarly it is possible to traverse a tree in several ways, and they result in different orders in which the nodes are visited.

#### Depth-First Traversal

One group of traversal methods is called depth-first traversal: for each child node, look at all of its child nodes before going on to the next child node. There are three ways this can be done, based upon whether the children of each child node are visited before the child node itself: pre-order traversal, in-order traversal, and post-order traversal. This is best explained by diagrams in the following table.

Pre-Order Traversal | In-Order Traversal | Post-Order Traversal |
---|---|---|

`F` , `B` , `A` , `D` , `C` , `E` , `G` , `I` , `H` | `A` , `B` , `C` , `D` , `E` , `F` , `G` , `H` , `I` | `A` , `C` , `E` , `D` , `B` , `H` , `I` , `G` , `F` |

#### Breadth-First Traversal

The other general class of tree traversal is breadth-first traversal, in which all the nodes at each level are visited before any of children are visited.

Breadth-First Traversal |
---|

`F` , `B` , `G` , `A` , `D` , `I` , `C` , `E` , `H` |

## Review

### In the Real World

- Trees are used to store a multitude of structured objects, including your file system and the HTML elements on a page in your browser.

### Self Evaluation

- How is a binary search tree (BST) different from a plain binary tree?
- What traversal method would you use in a sorted binary tree to visit the nodes in order of their contained values?
- A completely unbalanced binary search tree in which every node (except the root and leaf) has a single child, is essentially equivalent to which other data structure? What implication would this have for binary search tree lookup?

## Task

Create your own implementation of a binary search tree, implementing the following interface, complete with unit tests. For books with a range of publication dates, use the *starting* date of the range as the publication date. You may have to update your publication interface so that it returns some publication date for all publication types.

```
/** A binary search tree for publications that sorts by publication date. */
public interface PublicationBinarySearchTree {
/**
* Adds a publication to the BST.
* The publication will be sorted in the tree based upon its publication date.
* If a publication is already in the tree with the same publication date,
* no publication is added.
* @param The publication to add.
*/
void add(@Nonnull Publication publication);
/**
* Determines if a publication is contained in the tree
* with the publication date as the one given.
* @param publication The publication the date of which to search for.
* @return <code>true</code> if a publication is contained in the tree with the same publication date.
*/
boolean contains(@Nonnull Publication publication);
/**
* Prints all publications in the tree using depth-first in-order traversal.
* @implSpec This implementation uses the {@link Publication#toString()} method of each object in the tree.
* @deprecated This method is for learning and will be removed in the future.
*/
@Deprecated
void printAll();
}
```

After adding all your publication to a `PublicationBinarySearchTree`

(in no particular order) from the `Booker`

application, call the `PublicationBinarySearchTree.printAll()`

method to print out each publication in order of publication date.

Lastly, remove the `getFirstNode()`

method from your `LinkedList`

interface, which you added as a learning tool in a previous lesson. Your Booker application can still use the `LinkedList.get(int index)`

and `LinkedList.getLength()`

methods to iterate through the lists. As you might guess, retrieving objects from the middle of a linked list using index-based lookup is not very efficient, but you will learn a better approach for iterating through the elements in a linked list.

## See Also

- Data structures: Introduction to Trees (YouTube - mycodeshool)
- Data structures: Binary Search Tree (YouTube - mycodeshool)

## References

## Acknowledgments

- Pre-order, in-order, and post-order depth-first traversal tree diagrams are from the Wikimedia Commons, derived from diagrams by Miles, and placed in the public domain by Pluke.
- Breadth-first traversal tree diagram is from the Wikimedia Commons and was made available under the CC0 1.0 Universal Public Domain Dedication by Rory O'Kane.