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

• You only meet her once every three years
• 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 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 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

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 (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