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