BST CSCI 61

What is the definition of a Binary Search Tree (BST)?

A BST is a binary tree where for each node, every node in the left subtree is less than the root, and every node in the right subtree is greater than the root.

What happens if a Binary Search Tree is empty?

If the BST is empty, it simply contains no nodes and has no root, left, or right subtree.

What is the Binary Search Tree property?

For every node in the tree, all elements in the left subtree are less than the node, and all elements in the right subtree are greater than the node.

How does BST improve search efficiency compared to a regular binary tree?

BST allows binary search: halve the problem at each step by going left or right depending on the target value, which gives O(log n) time in a balanced tree.

What is the worst-case search time in a BST?

O(h), where h is the height of the tree.

What is the best-case height of a BST for efficient searching?

In a balanced BST, the height is log₂(n), giving the best-case efficiency for search.

How does a BST handle insertion of a duplicate key?

The BST ignores the insertion—duplicate keys are not added.

What is the process to find a key in a BST?

Start at the root. If the key is less than the root, search left; if greater, search right; if equal, return true.

What is the process to find the minimum value in a BST?

Traverse to the leftmost node; it holds the minimum value.

What is the process to find the maximum value in a BST?

Traverse to the rightmost node; it holds the maximum value.