We use cookies to ensure you have the best browsing experience on our website. Please read our cookie policy for more information about how we use cookies.
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).
Valid BST
You are viewing a single comment's thread. Return to all 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 !