Binary Search Tree Preparation

Overview

We’ll now consider another very useful kind of tree that maintains items in sorted order: a binary search tree.

Basic Learning Objectives

Before class, you should be able to:

• Describe what a binary search tree is
• Describe the differences between a binary tree and a binary search tree
• Describe the operations of a binary search tree

Advanced Learning Objectives

After class, you should be able to:

• Understand binary search tree operations and their implementations in Kotlin
• Analyze the run-time of binary search tree operations

Resources

You should read the following:

• 6.12 Binary Search Trees
• 6.13 Search Tree Operations
• 6.14 Search Tree Implementation
• 6.15 Search Tree Analysis

Checks

Submit answers to the following on Moodle. Drawing out the trees will be tedious, so feel free to draw out your answers, take a picture or screenshot, and put it on Moodle.

1. Which of the following binary trees are valid binary search trees? Why?

1. Given the following BST, what will it look like after trying to insert 42?

1. What will the same BST look like after trying to delete 49?

Acknowledgements

Check question from Prof. Jean Salac.