Binary Search Tree

Post order traversal :

• 1a+b*c+d*e+f*g

• 1abc*+de*f+g*+

• ++a*bc*+*defg

• abc+*+defg*+*

In Order traversal

• 40 20 50 10 30

• 40 50 20 30 10

• 10 20 30 40 50

• 50 40 20 30 10

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

Which method checks that two objects are equivalent?

• toString

• equals

• compareTo

• binarySearch

Binary Search works best on

• Equally effective on sorted and unsorted lists

• Unsorted lists

• Sorted lists

• None of the above

If the specified value is present binary search will return

• true

• false

• the value

• the position of the value