If a Binary Search Tree is constructed by inserting 10, 20, 30, 40 in this order, what type of tree is produced?

Options

  • A. Perfect binary tree
  • B. Balanced binary tree
  • C. Right-skewed tree
  • D. More than one of the above
  • E. None of the above

Correct Answer (Detailed Explanation is Below)

C. Right-skewed tree

Detailed Explanation

When 10, 20, 30 and 40 are inserted into a standard BST in increasing order, each new value is greater than the previous value. Consequently, every new node becomes the right child of the previous node. The resulting tree is called a right-skewed or degenerate BST. Its height becomes Nāˆ’1, causing search, insertion and deletion to degrade to O(N) in the worst case.