You are given a list of numbers that are forming a BST. You know the value of numbers but do not know the edges. You can call an API isParent(x,y) and it will return a boolean that is x a parent(exact parent not ancestor) of y. You have to reconstruct the BST using this API.
Appproach:
Smallest element is on the left
If you establish that a node is a child of a parent, then any other number in the range between parent and child must be in the right subtree of child. For example if (5)---parent-->(10) and we come across 9, it must be the case that 9 is in the right subtree of (5)
We can do the following:
Sort the list. Now we know the left most element of the tree, it is the first item in the list.
Is the next item the parent of [0]? No, continue
keep going until we find it's parent.
Once we find the parent, we know that the nodes in between [0:n] (where "n" is the parent node) is a subtree that is the right child of [0]
Divide and conquer, perform the same process on [1:n-1]. The goal is to build out that right subtree and attach it to the right of 0.
We know the smallest element in [1:n-1] is the left most child of the right subtree we're trying to find for [0]
etc...
Can anyone please help writing at least pseudocode for the above dividide and conquer? Thanks!