10 - Binary Search Trees

What is the MAXIMUM number of nodes in a binary search tree with height = 5 ?

• 2⁶-1

• 2⁵-1

• 2⁵

• 2⁶

• 6

What is the MINIMUM number of nodes in a binary search tree with height = 5?

• 6

• 5

• 2⁶-1

• 2⁵-1

• 2⁵

What is the worst-case runtime of lookUp/get in a binary search tree?

• O(n)

• O(logn)

• O(1)

• O(n²)

What is the worst-case runtime of lookUp/get in a *perfectly balanced* binary search tree?

• O(logn)

• O(n)

• O(1)

• O(n²)

When deleting from a binary search tree, if the node being deleted has 2 children, we replace the entry with ____.

• the inorder successor
• null
• the left child
• the right child
• the parent