Welcome to Lesson 9!
Learning ObjectivesBy the end of this class, you should know...
 What is a tree and how does it differ from a linked list?
 What is a Binary Tree ADT?
 What are the properties of Binary Trees?
 How do you determine if a Binary Tree is balanced?
1. Tree ADT
1.1. 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.
1.2. 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.
1.3. 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.
1.4. Reflection: 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
 Siblings
 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.
2. The Binary Tree ADT
2.1. Defining a Binary Tree
 A binary tree is a tree where each node can have at most 2 children.
 Below is an example of a binary tree. Note that each node has 0, 1 or 2 children.
Image source
 Here is another example of a valid binary tree. Why does this tree meet the definition of a binary tree?
 Reflection: Is the below image a valid BT? Why or Why Not? Also, what does it resemble?
Image source. These two children are called the left child and the right child.
 For example, in the BT above, 4 is the left child of its parent node 6 and 7 is the right child of its parent node 6.
 14 only has a left child, but does not have a right child.
 We can consider binary trees to be recursive structures.
 The root node links to root nodes of its left and right subtrees.
 These roots of the subtrees in turn link to the root nodes of their left and right subtrees.
 We will discuss this concept more when we get to Binary Search Trees.
Image source.
 Therefore,
each node in the tree will contain some data as well as two references,
one to the left child and one to the right child as depicted below:
 If a node has no right or left child, these values are set to Null.
 As
you might have predicted, when we go to implement the binary search
tree, we will be representing its node as a private inner class like
this:
private class Node { T data; Node left; Node right; }
 Therefore, a Node has three fields:
 a field for the data
 a field for the address of the left child (another Node).
 a field for the address of the right child (another Node).
 A binary tree is made up of Nodes, each with pointers to a left and right child node as shown below:
2.2 Special Types of Binary Trees A binary tree is considered a proper or strict binary tree if each node has either 0 or 2 children. Below is an example of a strict binary tree.
 A complete binary tree is one in which all levels are filled (except the last) and all nodes are as far left as possible. Below is an example of a complete binary tree.
 A perfect or full binary tree is one in which all levels are completely filled.
2.3. Balanced Binary Trees
 The above trees are examples of balanced trees.
 In balanced trees, operations will be more efficient  as we shall discuss later.
 But what does balanced mean?
 There are several ways to define a balanced tree.
 We shall use the definition from a special type of balanced tree known as an AVL tree.
 A balanced binary tree is one in which the difference between the height of the left and right subtrees is not more than 1.
 height_{left}  height_{right} <= 1
 Let's give this a try.
 The below tree is balanced even though it might not appear so. Why?
 Consider the height of the right and left subtree of the root node A.
 h_{left} = 1 (height of C)
 h_{right} = 2 (height of B)
 1  2 = 1 <balanced!
 Let's check another node, B.
 h_{left} = 1 (height of a null is defined to be 1)
 h_{right} = 0 (height of D)
 1  0 = 1 <balanced!
2.4. Reflection  Is the binary tree depicted below balanced? Why or why not?
Image source.
Wrap Up
 Answer the review questions on Canvas for today's lesson
Upcoming Assignments.
 Lab due Monday
 Study for Your Quiz!
