State true or false? Binary search tree requires a sorted list Linear search…

Concept

• A binary search tree (BST) is built by inserting keys one at a time: each new key is compared against existing nodes and placed on the branch that keeps every left descendant smaller and every right descendant larger. This insertion process is what creates the ordering — the input list itself never needs to arrive pre-sorted.

• A linear search scans a list from the front, examining one element at a time until it finds a match or reaches the end. For a list of n elements, this needs at most n comparisons — an amount that grows in direct proportion to n, not to its square.

• This is different from the classic binary search algorithm on an array, which does need the array sorted first. A binary search tree is a separate data structure: its ordering comes from where each key lands during insertion, not from any pre-sorting of the input list.

Application

1. Statement 1 claims a BST requires a sorted list. Since the ordering is built up key by key during insertion rather than assumed from the input, statement 1 does not hold.

2. Statement 2 claims linear search takes n^2 comparisons. Since a linear scan checks each element once as it moves through the list, its comparison count is n, not n^2, so statement 2 does not hold either.

Cross-check

1. Insert the unsorted sequence 5, 1, 8, 3 into an empty BST one key at a time: 5 becomes the root; 1 is smaller than 5, so it becomes the left child of 5; 8 is larger than 5, so it becomes the right child of 5; 3 is smaller than 5 but larger than 1, so it becomes the right child of 1. A valid BST results even though the input was never sorted, confirming statement 1 is false.

2. Scan the 4-element list [5, 1, 8, 3] left to right for a target value: at most 4 comparisons are needed, one per element, not 4^2 = 16, confirming statement 2 is false too.

Both statements are false, so the correct combination is False, False.