BPSC TRE Data Structures & Algorithms – Full Subject Test 2

$A binary tree of height H has max nodes = 2^0 + 2^1 + ... + 2^H = 2^{H+1} - 1.$

BST ordering is left < root < right. Therefore inorder traversal produces non-decreasing order, and with distinct keys it is strictly increasing. All three statements are correct.

Because a BST enforces Left < Root < Right, an Inorder traversal (Left, Root, Right) processes keys in non-decreasing sorted order.

AVL and Red-Black trees maintain logarithmic height through their balancing rules, giving O(log N) worst-case search. All three statements are correct.

Self-balancing binary search trees maintain height bounded by O(log N), guaranteeing search, insertion, and deletion in O(log N) worst-case time.