About a particular test case in problem 15.11 - TEST IF THREE BST NODES ARE TOTALLY ORDERED


Write a program which takes two nodes in a BST and a third node, the “middle”
node, and determines if one of the two nodes is a proper ancestor and the other a
proper descendant of the middle. (A proper ancestor of a node is an ancestor that
is not equal to the node; a proper descendant is defined similarly.) For example, in
Figure 15.1 on Page 255, if the middle is Node /, your function should return true if
the two nodes are {A,K] or j/, M|. It should return false if the two nodes are [1,P| or
{],K}. You can assume that all keys are unique. Nodes do not have pointers to their

The test case in question

Test FAILED (441/959)
tree: [“18”, “9”, “29”, “5”, “14”, “21”, “34”, “1”, “null”, “null”, “17”, “null”, “25”, “null”, “35”]
possible_anc_or_desc_0: 17
possible_anc_or_desc_1: 9
middle_idx: 9

Failure info
expected: True
result: False

If i understand the question, 17(possible_anc_or_desc_0) is a proper descendant of middle(whose value is 9). if we consider this scenario, then 9(possible_anc_or_desc_1) must be the possible ancestor of middle. it is an ancestor, but clearly not a proper ancestor. therefore the result must be False. but why is the expected result True?

(ofcourse the scenario of considering possible_anc_or_desc_0 as proper ancestor of middle is ruled out as its not an ancestor of middle)

1 Like