I have an assignment that asks for this. So I am not looking for the answer itse

Question

I have an assignment that asks for this. So I am not looking for the answer itself but a hint on how to find a value that will always break the BST condition by myself.

If I have access to any node N of a BST that has at least 2 nodes in its root, and where every node will always be different.

If I were to replace N.key with x, what should the value of x be in order for the tree not to be a BST anymore?

I can use the following operations: GetPre = key before N when seen from an inorder transverse.

GetSuc = key after N when seen from an inorder transverse.

MAX = gets the node value from the sub-tree that has N as root.

MIN = gets node value from the sub-tree that has N as root.

I broke it in several subcases, but I am sure this can be written as one single formula.

I came up with:

x=N.key?GetPre(N) but it doesn't work as I expected.

I appreciate any insight.

Explanation / Answer

Hint: In a BST, an inorder traversal produces the keys in sorted order. If we had N.key = 20 and the inorder traversal was 2,4,10,11,17,20,28,31,40, what x values would break the sorted order when put in the place of 20?

Related Questions

Navigate

• Browse (All)
• Browse I
• Subjects

Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.