# Trees

## Why organize data as a tree structure?

- Humans have a natural inclination towards hierarchical thinking and this have had a profound impact on the way we reason, decide and look at
*things*
- Examples are social and political structures such as
*family tree*, *governance* and *species*
- Introducing
*order* such as *hierarchical order* to data allows computers to make decisions in a much more efficient way then linear data structures

## Example: Visiting a distant aunt

What do we know about this aunt and our family:

- You only meet her once every three years
- She is from your
**dadâ€™s side**
- There is a huge family gathering next week and you have been asked to find her address.

## Example: Visiting a distant aunt

- Equipped with the knowledge from the previous week, we would organize family relatives in the following fashion:

## Example: Visiting a distant aunt (2)

Knowing the hierarchical **order** of our family, we would prefer making a family tree!

## Order

- Provides the computer additional insights on the relation between data values
- Allows the computer to examine the relationship between data values and make decisions based on them
- This makes lookup for a data value much faster, we can avoid examine a large chunk of the data set
- In the example, we knew the aunt was on the dadâ€™s side and thus avoided looking into momâ€™s side of relatives!
- A tree is an example of organizing data values according to an
**order** (e.g hierarchical order)

## Tree terminology

## Tree Properties

A tree constitute with the following properties:

- A single & special node named
**root**, start node on top of tree and does not have a **parent**
- Succeeding nodes can be either a
**child** or **parent**
- A
**child** node is connected by *at-least* a preceding node
- The
*preceding* node is known as a **parent** node
- A
**parent** node has *zero, one or more* children(successor nodes)

## Subtrees

## Subtrees Properties

- All nodes in a tree (except the
**root**) are child nodes
**Siblings** are nodes with the same **parent**
**Subtree** are the descendants of a node
- A node without children is a
**leaf** node

## Tree Height

## Tree Depth

## Path

## Traversal Methods

Linear data structures have only one way to read data; a tree can be traversed in two ways: **depth-first** and **breath-first**(discussed next week). Three depth-first methods:

- Pre-order
- In-order
- Post-order

## Traversal Methods (1)

## Traversal Methods (3)

Visit Nodes in a recursive fashion

**Pre-order traversal**

`root node => left sub-tree => right sub-tree`

**In-order traversal**

`left sub-tree => root node => right sub-tree`

**Post-order traversal**

`left sub-tree => right sub-tree => root node`

## Binary Trees

- Each node contains a
**data value**
- Branching at each node occur either at
**left** or **right**
- A binary tree can be composed of zero, one or two children
- Useful for Searching: Traversing either
**left** or **right** to find the target