Question

1. Assume the key of the right child below the root node of a binary search tree is 40. The value in the root node could be ________.

2. On average, searching for an item in a balanced binary search tree is _________ operation.

3. Where is the inorder successor of a node A in a binary search tree?

Answer 1

1) The key of the right child below the root node of BST is 40. The right child has values greater than the root node. So all values which are less than 40 can be in the root node

2) In a balanced BST, searching is a O(log n) operation as we have all elements arranged in order. Elements left of root node contain lesser values and right elements contain greater value.

3) The inorder successor of a node A in a BST is the next node in the inorder traversal of the BST