DCS2101 - Week 10 (Trees)

Multiple Select

If you had to organize 100 candies in such a way that you can always find your favorite one really fast — would you:

• Pile them randomly

• Sort them neatly in one line

• Arrange them in a branching candy tree

Open Ended

What are some real-life examples of hierarchical structures that can be represented as trees?

Multiple Choice

What does BST stand for?

• Binary Search Technique
• Binary Search Tree
• Basic Sorting Tree
• Balanced Search Tree

Multiple Choice

The topmost node of a tree is called the:

• leaf
• branch
• trunk
• root

Multiple Choice

How many children can a node have in a binary tree?

• 4
• 3
• 1
• 2

Open Ended

If your phone’s folders and apps were organized as a tree, who would be the root node and what would the leaves represent?

Multiple Choice

In a BST, where are all smaller elements found?

• All smaller elements are found in the right subtree.
• All smaller elements are found at the root.
• All smaller elements are found in a separate list.
• All smaller elements are found in the left subtree.

Multiple Choice

Which traversal visits the root last?

• Post-order traversal
• Level-order traversal
• Pre-order traversal
• In-order traversal

Multiple Choice

What is the inorder traversal for: 5 → left 3, right 7?

• 5, 3, 7
• 3, 5, 7
• 3, 7, 5
• 7, 5, 3

Multiple Choice

If a BST has 7 nodes, how many edges does it have?

• 6
• 8
• 7
• 5

Multiple Choice

When deleting a node with one child, we:

• Promote the child to the parent node.
• Replace the node with a null value.
• Delete the node without any changes.
• Replace the node with its child.

Multiple Choice

In BST deletion, if the node has two children, we replace it with:

• the node itself
• the left child
• the right child
• in-order successor

Draw

Draw a Binary Search Tree for the values:
8, 3, 10, 1, 6, 14, 4, 7

Draw

Given this BST:

12

/ \

8 15

/ \ \

5 10 20

What happens when you delete 8?

And now a word from our sponsor...