# Valid BST

# Valid BST

ezequiel + 0 comments 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 !

- AD
alokdube1978 + 0 comments 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?

PoojaJeyaprakash + 4 comments 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..

abhiranjanChallenge Author + 0 comments Hi @PoojaJayaprakash, sorry can't get where you are referring to by

*nth*element. Are you considering the preorder listing while considering*nth*element?PoojaJeyaprakash + 0 comments @abhiranjan thank you i figured that out myself

- MV
mvyavahare9 + 0 comments how to submit the code in c language???

abhiranjanChallenge Author + 0 comments Hi @mvyavahare9, this is a functional programming track, where you can submit in only those languages which support functional paradigm.

- DG
djgorman + 0 comments 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

Sort 4 Discussions, By:

Please Login in order to post a comment