Welcome Back!

Learning Objectives
By the end of this class, you should know...
  • Big-O Notation
  • Trees, Binary Trees

Announcements

  • Midterm 1 next class
  • Lab 5 posted


Finish Algorithm Efficiency


Tree ADTs

Introducing Trees
  • Consider the ADTs we have studied so far:
    • Array
    • Linked List
    • Queue 
    • Stack
  • These structures all store data in a linear fashion, as in the example of a linked list show below:
  • However, storing data linearly is not the only option.
  • In many cases, our data might not have a linear relationship.
  • Consider, for example, a company's org. chart:

  • Or, consider this depiction of the relationship among the countries in the world and their cities and states:
Image source.

  • Or, consider this data which is arranged into what we call a decision tree:

Image source.

  • Given the nature of certain types of data, sometimes it can make more sense to organize the data in hierarchical structure.
  • Also, certain operations, such as search and insertion or deletion can be more efficient when we organize data hierarchically rather than linearly.
  • In computer science, we can use a tree ADT to organize data hierarchically.

The Structure of the Tree ADT
  • Like linked lists, trees are comprised of nodes.
  • These nodes store data and pointers to other nodes in the tree.
  • Like the head and tail of a linked list, trees have specially-named nodes that serve important functions in the tree.
  • The most important node is known as the root.
  • Like the head of a linked list, a root is what allows us to access the first node in the tree.
  • You can visualize a tree ADT with its root node like this:


  • Trees in computer science are usually depicted with the root node on top.
  • Therefore, you have to visualize the tree upside down.


  • The branches of the tree are called links or edges.
  • Unless the tree is empty or has size==1, each Node in the tree is connected to other nodes by these pointers (links).
  • Nodes in a tree have parent-child relationships.
  • Each node can have only one parent node. But a node can have 0 or more child nodes.
  • The root node in the image below has four child nodes.
  • The root is considered the parent node of those four child nodes.
  • For example, A is considered the child node of the root and the root is considered the parent node of A.

  • In other words, the terminology we use to describe trees and their nodes, is similar to that of a family tree.


  • Nodes in a tree can have parents, grandparents, cousins, siblings, children and grandchildren.
  • They can also have ancestors and descendants.
  • For example, in the tree below, Nodes 1,4,7, and 10 and their parents are all descendants of the the root node 5.
  • The root node 5 is thus their ancestor.

Tree graph example

  • Another important node in a tree is the leaf node.
  • The leaf node is any node in the tree with no children.
  • In other words, the links of a leaf node point to Null.
  • Any node that is not the root or a leaf is called an interior node as depicted above.
  • The root and leaves of the tree are exterior nodes.

Properties of Trees
  • Consider a tree with n nodes. How many edges will it contain.
    • Exactly n-1. Why is this the case?
    • The reason is that all nodes, except the root, have exactly one incoming edge.
  • The depth of a node X in a tree is defined as the number of edges from the root to the node X.
    • What is the depth of the root node, given this definition?
  • The height of a node X is defined as the number of edges in the longest path from the node X down to a leaf node.
    • What is the height of any leaf node given this definition?
  • Trees themselves can also have heights. The height of any tree is the same as the height of its root.




Activity Labeling a Tree
  • Given the tree below, answer the following questions:


  • Step 1: Label the root and leaf nodes
  • Step 2: List at least one of each of the following relationships:
    • Parent-child
    • Child-parent
    • Siblings
    • Cousins
    • Grandparent-grandchild
    • Ancestor
    • Descendant
  • Step 3: identify 3 interior nodes
  • Step 4: label the depth of the following nodes:
    • /
    • -
    • f
    • g
    • 2 (both of them)
  • Step 5: label the height of the same nodes.




Upcoming Assignments

  • Lab 5 due on Tuesday
  • Midterm 1 next class