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
Example
