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