Sort 5 Discussions, By:
Please Login in order to post a comment
It is nice to learn the fact that the preorder let you know the order in which the elements were inserted.
I didn't reconstructed the tree though.
[SPOILER of a non optimal solution]
If the list is null then the answer is YES
If it is not null I took the head, then took the tail and split it in a tuple (tail.takeWhile(x < head), tail.dropWhile(x < head))
With this you just check than all elements in tail.dropWhile(x < head) are greater than the head and check recursively the remaining two lists to see that they are BST's too.
Of course this can be optimized, I think it would be n·log n if you refine it well. This was just an idea that I tried and worked, but as mentioned in the comments this can be solved in O(n).
Really nice and fun challenge @abhiranjan !
python, java or cpp are not in the list :(
Can a new node be two levels up? For example can we go 3 1 2 7 9 10 6
6 will be a child of 7 but still one node above 9 and 10
Normally we just go one node up. For example 8 would be valid instead of 6.
So is the above a valid input?
Given the preorder of a tree v can obtain the inorder of the same tree by organizing the contents in the ascending order and with both preorder and the inorder we can construct the Tree and validate if its a BST..
Hi @PoojaJayaprakash, sorry can't get where you are referring to by nth element. Are you considering the preorder listing while considering nth element?
@abhiranjan thank you i figured that out myself
how to submit the code in c language???
Hi @mvyavahare9, this is a functional programming track, where you can submit in only those languages which support functional paradigm.
This can actually be solved without constructing the tree (that is, building a tree structure in memory). Just need to know what state info is necessary to support the insertion rules at each point in the list. And it's O(n). :)
No more comments