Welcome to Lesson 9!

Learning Objectives
By 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 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.

1.3. 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.




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:
    • Parent-child
    • Siblings
    • Ancestor
    • Descendant
  • Step 3: identify 3 interior nodes
  • Step 4: label the depth of the following nodes:
    • html
    • body
    • li

  • 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:
Binary Tree
  • 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.
| heightleft - heightright| <= 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.
  • hleft = 1 (height of B)
  • hright = 2 (height of C)
  • |1 - 2| = 1 <--balanced!
  • Let's check another node, B.
  • hleft = -1 (height of a null is defined to be -1)
  • hright = 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