Welcome Back!Learning ObjectivesBy the end of this class, you should know...Big-O NotationTree ADTAnnouncementsMidterm 1 next classReturn quizzesLab 5 postedProject Report 1 gradedAdvice: Take these reports seriously. Worth 10% of project grade.Finish Algorithm EfficiencyTree ADTsIntroducing TreesConsider the ADTs we have studied so far:ArrayLinked ListQueue StackThese structures all store data in a linear fashion, as in the example of a linked list show below:Image sourceHowever, 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: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 ADTLike 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:Image sourceTrees in computer science are usually depicted with the root node on top.Therefore, you have to visualize the tree upside down.Image sourceThe 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.Image sourceIn 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.Image sourceAnother 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 TreesConsider 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.Image source.Activity Labeling a Tree Given the tree below, answer the following questions:Image source.Step 1: Label the root and leaf nodesStep 2: List at least one of each of the following relationships:Parent-childSiblingsGrandparent-grandchildAncestor-DescendantStep 3: identify 3 interior nodesStep 4: label the depth of the following nodes:26, 41, 10, 28Step 5: label the height of the same nodes.Upcoming AssignmentsLab 5 due on MondayMidterm 1 next class