Activity: Trees

Learning Objectives:

• Use appropriate terminology to describe binary trees
• Perform traversals on binary trees
• Write code to implement parts of binary trees and traversals

Time to Complete: 50 minutes

Submission: Submit individual PDF to Canvas

Instructions:

For these activities, follow the steps closely. Your goal is to complete all parts of the activity within the time provided.

If a section is hidden behind a "Continue" button, you should make sure that you have completed the previous sections and answered any questions before moving on. Do not skip ahead or reveal any solution until you have completed the previous steps.

Collaboration Encouraged

I encourage you to work with a partner or in a small group (no more than three) for in-class activities! Feel free to divvy up roles, compare solutions, and learn from each other.

If the assignment requires you to submit your work, make sure to include the names of all team members in the submission.

Your Name(s):

---

Part 1: Parts of a Tree

(20 minutes)

Continue

Consider the following tree:

graph TB;
    A((A))-->B((B))
    A-->C((C))

1. Each of the circles represents a node in the tree.

   How many nodes are in the tree?

2. Each node has a value and connects to at most two other nodes (a left node and a right node). These connections are called edges.

   How many edges are in the tree?

Solutions

There are 3 nodes in the tree and 2 edges.

Continue

Relationships

Now consider this tree:

graph TB;
    A((A))-->B((B))
    A-->C((C));
    B-->E((D))
    B-->F((E))
    C-->H((F))
    C-->I((G))

1. Consider the following definitions:

   • Parent: The node that points to a node from above.
   • Children: The nodes that a node points to below.
   • Root: A node with no parent.
   • Leaf: A node with no children.

2. Answer the following questions about the tree:

   • What is the parent of node B?

   • What are the children of node C?

   • What is the root of the tree?

   • How many leaves are there?

   Solutions

   • The parent of node B is node A.
   • The children of node C are nodes F and G.
   • The root of the tree is node A.
   • There are four leaves in the tree: nodes D, E, F, and G.

Continue

3. You can think about the tree like a "family tree"! Consider the leaf node D.

   • Fill in the blank: Node B is the ______ of node D.

   • Fill in the blank: Node A is a(n) ______ of node D.

   • Fill in the blank: Node E is a(n) ______ of node D.

   Solution

   • Node B is the parent of node D.

   • Node A is an ancestor of node D.

     • You may have said "grandparent", which is also correct, but we typically use ancestor to refer to any node above another node.
     • This also means that node D is the descendant of node B and also node A.

   • Node E is a sibling of node D.

     • This means that nodes D and E share the same parent, node B.

Continue

Paths and Depth

Consider this tree:

graph TB;
    A((H))-->B((C))
    A-->C((B))
    B-->D((A))
    B-->E((F))
    C-->F((E))
    E-->H((D))
    E-->I((G))
    C~~~G((X)):::hidden

    classDef hidden display: none;

1. A path is a sequence of nodes where each node is connected to the next by an edge.

   • What is the path from node H to node A?
     Solution

     The path from node H to node A is: H → C → A.

2. The length of a path is the number of edges in the path.

   • What is the length of the path from node H to node A?
     Solution

     The length of the path is 2, since there are two edges in the path.

3. The depth of a node is the length of the path from the root to that node. We consider nodes with the same depth to be on the same level.

   • What is the depth of node A?

   • What nodes are on level 1?
     Solutions

     • The depth of node A is 2.
     • Nodes C and B are on level 1.

4. The height of a tree is the maximum depth of any node in the tree.

   Common Misconception

   Don't count the nodes when determining the height. Count the number of edges from the root to the furthest leaf.

   The root doesn't count as a level, so the height of a tree with only a root is 0.

   • What is the height of the tree?
     Solution

     The height of the tree is 3.

Continue

Balanced Trees

Take a look at these two trees, that each have 7 nodes:

Tree A	Tree B
graph TB; A((A))-->B((B)) A-->C((C)) B-->E((D)) B-->F((E)) C-->H((F)) C-->I((G))	graph TB; A((A))-->B((B)) A-->C((C)) B-->E((D)) B-->F((E)) E-->H((F)) E-->I((G)) classDef hidden display: none;

1. Answer the following questions:

   • What is the height of Tree A?

   • What is the height of Tree B?

   • Note that a binary tree has at most two children per node, but you could have nodes with only one child or no children.

Continue

2. Let's generalize. Think about a tree with n nodes.

   • What is the minimum height of a binary tree with n nodes?
     Hint

     Tree A is an example of the ideal way to make a tree as short as possible.

   • What is the maximum height of a binary tree with n nodes?
     Hint

     Imagine if every node had only one child. How many edges would you need to connect n nodes?

   Solutions

   • The minimum height of a binary tree with n nodes is \(\lfloor log_2\ n \rfloor\).
   • The maximum height of a binary tree with n nodes is \(n - 1\).

Continue

3. Tree A is an example of a balanced tree:

   • A balanced binary tree is a binary tree where the height of the left and right subtrees of every node differ by at most one.

   • A subtree is a subset of a tree. Imagine cutting off a branch of a tree and looking at the smaller tree that remains.

     • For example, in Tree A, the left subtree of Node A is:

       graph TB;
           B((B))
           B-->D((D))
           B-->E((E))

4. Is Tree B a balanced tree? Why or why not?
   Solution

   • Tree A is a balanced tree because the height of the left and right subtrees of every node differ by at most one.
   • Tree B is not a balanced tree because the height of the left and right subtrees of node A differ by two.

Continue

Full and Complete Trees

1. There are two other types of trees that are related to balanced trees: full trees and complete trees.

   • A full binary tree is a binary tree where every node has either zero or two children. (One child is not allowed.)

   • A complete binary tree is a binary tree where every level is completely filled except possibly for the last level, which is filled from left to right.

2. Consider the following tree:

   graph TB;
       A((C))-->B((I))
       A-->C((F))
       C-->D((B))
       C-->E((G))

   • Is this tree full, complete, or neither? Explain.
     Solution

     Full:

     • This tree is full because every node has either zero or two children.
     • This tree is not complete because the last level is not as far left as possible.

3. Consider the following tree:

   graph TB;
       A((C))-->B((I))
       A-->C((F))
       B-->D((B))
       C-->E((G))
       B~~~F((E)):::hidden
       C-->G((A))
   
       classDef hidden display: none;

   • Is this tree full, complete, or neither? Explain.
     Solution

     Neither:

     • This tree is not full because node F has only one child.
     • This tree is not complete because the last level is not filled from left to right.

4. Consider the following tree:

   graph TB;
       A((C))-->B((I))
       A-->C((F))
       B-->D((B))
       B-->E((G))
       C-->F((E))
       C~~~G((X)):::hidden
   
       classDef hidden display: none;

   • Is this tree full, complete, or neither? Explain.
     Solution

     Complete:

     • This tree is complete because every level is completely filled except possibly for the last level, which is filled from left to right.
     • This tree is not full because node F has only one child.

Continue

5. Finally, there is the concept of a perfect tree:

   • A perfect binary tree is a full binary tree where all leaves are at the same level.

   • Here is an example:

     graph TB
         A((A))-->B((B))
         A-->C((C))
         B-->D((D))
         B-->E((E))
         C-->F((F))
         C-->G((G))
         D-->H((H))
         D-->I((I))
         E-->J((J))
         E-->K((K))
         F-->L((L))
         F-->M((M))
         G-->N((N))
         G-->O((O))

6. What about this tree:

   graph TB;
   A((A))-->B((B))
   A-->C((C));

   • Is this tree perfect? Explain.
     Solution

     Yes, it is full, and all leaves are at level 1.

---

Part 2: Traversals

(30 minutes)

Continue

Take a look at the code for Node:

public class Node {
    public int value;
    public Node left;
    public Node right;
    ...
}

It's just like a linked list, but with two references instead of one!

Continue

Pre-Order Traversal

Consider the following pseudocode:

def preorder(node):
    if node is null:
        return

    print(node.value)
    preorder(node.left)
    preorder(node.right)

1. Consider the following tree:

   graph TB;
       A((A))-->B((B))
       A-->C((C));
   
       classDef hidden display: none;

   • Imagine we call preorder(A), where A is the root node. Trace through the execution of the code. Use scratch paper!

     What will be printed when preorder(A) is called?
     Solution

     The output will be: A, B, C.

Continue

2. Consider the following tree:

   graph TB;
       A((A))-->B((B))
       A-->C((C));
       B-->E((D))
       B-->F((E))
       C~~~I((X)):::hidden
       C-->H((F))
   
       classDef hidden display: none;

   • What will be printed when preorder(A) is called?
     Solution

     The output will be: A, B, D, E, C, F.

Continue

In-Order Traversal

Consider the following pseudocode:

def inorder(node):
    if node is null:
        return

    inorder(node.left)
    print(node.value)
    inorder(node.right)

• What is the difference between preorder and inorder traversal?
  Solution

  • In preorder, we print the value of the node before visiting the left and right children.
  • In inorder, we print the value of the node after visiting the left child but before visiting the right child.

Continue

1. Consider the following tree:

   graph TB;
       A((A))-->B((B))
       A-->C((C));
   
       classDef hidden display: none;

   • What will be printed when inorder(A) is called?
     Solution

     The output will be: B, A, C.

Continue

2. Consider the following tree:

   graph TB;
       A((A))-->B((B))
       A-->C((C));
       B-->E((D))
       B-->F((E))
       C~~~I((X)):::hidden
       C-->H((F))
   
       classDef hidden display: none;

   • What will be printed when inorder(A) is called?
     Solution

     The output will be: D, B, E, A, C, F.

Continue

Post-Order Traversal

Consider the following pseudocode:

def postorder(node):
    if node is null:
        return

    postorder(node.left)
    postorder(node.right)
    print(node.value)

1. Consider the following tree:

   graph TB;
       A((A))-->B((B))
       A-->C((C));
   
       classDef hidden display: none;

   • What will be printed when postorder(A) is called?
     Solution

     The output will be: B, C, A.

Continue

2. Consider the following tree:

   graph TB;
       A((A))-->B((B))
       A-->C((C));
       B-->E((D))
       B-->F((E))
       C~~~I((X)):::hidden
       C-->H((F))
   
       classDef hidden display: none;

   • What will be printed when postorder(A) is called?
     Solution

     The output will be: D, E, B, F, C, A.

Continue

Traversal Tricks

So we have three traversal methods:

• Pre-order: node, left, right
• In-order: left, node, right
• Post-order: left, right, node

1. Take a look at this article, which talks about drawing dots around a tree and imagining a snake crawling around it.

2. Now, consider this tree:

   graph TB
       A((A))-->B((B))
       A-->C((C))
       B-->D((D))
       B-->E((E))
       C-->F((F))
       C-->G((G))
       D-->H((H))
       D-->I((I))
       E-->J((J))
       E~~~K((X)):::hidden
   
       classDef hidden display: none;

   • Use the snake trick to determine the pre-order, in-order, and post-order traversals.

     • You may want to draw the tree on a piece of paper and draw dots around it to help you visualize the snake.

   • What is printed by the pre-order traversal of the tree?

   • What is printed by the in-order traversal of the tree?

   • What is printed by the post-order traversal of the tree?

   Solutions

   • Pre-order: A, B, D, H, I, E, J, C, F, G
   • In-order: H, D, I, B, J, E, A, F, C, G
   • Post-order: H, I, D, J, E, B, F, G, C, A

Continue

Mystery Traversal

Consider this pseudocode:

def mystery(root):
    queue = new Queue()
    queue.enqueue(root)

    while queue is not empty:
        current = queue.dequeue()
        print(current.value)

        if current.left is not null:
            queue.enqueue(current.left)

        if current.right is not null:
            queue.enqueue(current.right)

1. Consider the following tree:

   graph TB;
       A((A))-->B((B))
       A-->C((C));
   
       classDef hidden display: none;

   • Trace through the code. You will want to draw the queue on a piece of paper to help you keep track.

   • What will be printed when mystery(A) is called?
     Solution

     The output will be: A, B, C.

Continue

2. Consider this tree:

   graph TB;
       A((A))-->B((B))
       A-->C((C));
       B-->E((D))
       B-->F((E))
       C~~~I((X)):::hidden
       C-->H((F))
   
       classDef hidden display: none;

   • What will be printed when mystery(A) is called?
     Solution

     The output will be: A, B, C, D, E, F.

Continue

3. What does the mystery function do?
   Solution

   • The mystery function performs a breadth-first traversal, also known as a level-order traversal.
   • It prints nodes on each level from left to right, going down the tree level by level.
   • This is different from the other traversals, which are depth-first traversals.

---

Part 3: Binary Search Trees Preview

(remaining time)

Continue

1. Consider this tree:

graph TB;
    A((8))-->B((3))
    A-->C((10))
    B-->D((1))
    B-->E((6))
    C-->F((9))
    C-->G((14))
    E-->H((4))
    E-->I((7))

1. Take a look at all the nodes to the left of the root.

   • What is the relationship between the root and the values to the left?

2. Now, take a look at all the nodes to the right of the root.

   • What is the relationship between the root and the values to the right?

3. Do you notice a pattern? Does this hold up for all nodes in the tree?

   • What is the pattern you see?

Solutions

• All nodes to the left of a node have values less than the node's value.
• All nodes to the right of a node have values greater than the node's value.
• This pattern holds for all nodes in the tree.

Continue

4. This is called a binary search tree (BST). A BST is a binary tree where for every node:

   • All nodes to the left have values less than the node's value.
   • All nodes to the right have values greater than the node's value.

5. Imagine I was looking for the value 7 in the tree. Start at the root.

   • Is 7 greater than or less than the value at the root?

   • Would the value 7 (if it exists) be in the right or the left subtree?

Solutions

• 7 is less than the value at the root (8).
• The value 7 would be in the left subtree.

Continue

6. Now, imagine we had the following subtree:

   graph TB;
       B((3))
       B-->D((1))
       B-->E((6))
       E-->H((4))
       E-->I((7))

   • Let's continue the search for the value 7. Start at the root of this subtree.

   • Is 7 greater than or less than the value at this root?

   • Would the value 7 (if it exists) be in the right or the left subtree?

Solutions

• 7 is greater than the value at the root (3).
• The value 7 would be in the right subtree.

Continue

7. Finally, consider this subtree:

   graph TB;
       E((6))
       E-->H((4))
       E-->I((7))

   • Let's continue the search for the value 7. Start at the root of this subtree.

   • Is 7 greater than or less than the value at this root?

   • Would the value 7 (if it exists) be in the right or the left subtree?

   • Do we find the value 7 in this subtree?

Solutions

• 7 is greater than the value at the root (6).
• The value 7 would be in the right subtree.
• We find the value 7 in this subtree.

Continue

8. Generalize the process of searching for a value in a BST.

   • Write pseudocode for a function that searches for a value in a BST.
   Parameters

   • The function should take two parameters: a node and a value.
   • Example: search(root, 7)
   Recursion

   • You will likely want to use recursion to search through the tree.
   Base Case

   • What is the base case for the recursion?
     • If the node is null, let's just return null.
     • If we find the value, let's return the node.
   Solution

   def search(node, value):
       if node is null or node.value == value:
           return node
   
       if value < node.value:
           return search(node.left, value)
       else:
           return search(node.right, value)
   

9. Now, think about performance. Assume the tree is balanced.

   • What is the worst-case time complexity of searching for a value in a BST?
   Solution

   The worst-case time complexity is \(\Theta(h)\), where h is the height of the tree. For a balanced tree, this is \(\Theta(log\ n)\). For an unbalanced tree, this is \(\Theta(n)\).

---

Submission

For these activities, you will typically submit a PDF report to Canvas. First, click the "Export as PDF" button below.

Export as PDF Reset Activity

Hide All Show All

Then, submit the PDF to Canvas. Everyone must submit their own copy to receive credit.