Welcome Back!
Learning ObjectivesBy the end of this class, you should know...
 BigO 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 speciallynamed 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 parentchild 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.
 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 n1. 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:
 Parentchild
 Childparent
 Siblings
 Cousins
 Grandparentgrandchild
 Ancestor
 Descendant
 Step 3: identify 3 interior nodes
 Step 4: label the depth of the following nodes:
 Step 5: label the height of the same nodes.
Upcoming Assignments  Lab 5 due on Tuesday
 Midterm 1 next class
