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.
  • Hackerrank Home
  • Prepare
    NEW
  • Certify
  • Compete
  • Career Fair
  • Hiring developers?
  1. Prepare
  2. Functional Programming
  3. Functional Structures
  4. Valid BST
  5. Discussions

Valid BST

Problem
Submissions
Leaderboard
Discussions

Sort 8 Discussions, By:

votes

Please Login in order to post a comment

  • denis631
    3 years ago+ 0 comments

    Good approach is to just simulate preorder traversal. Since we know how the sequence is built we try to consume the elements in the order they are given to use. If the next element does not fit into our contraints of lo (lower bound) and hi (upper bound) then we propagate to the parent.

    As the result, running preorder on a valid sequence will consume all elements, otherwise if the sequence could not be fully consumed a non-empty sequence of the remaining elements will be returned.

    This could be easily mapped to YES/NO

    preorder [] lo hi = []
    preorder (x:xs) lo hi = if lo < x && x < hi then rest else x:xs
        where remain = preorder xs lo x
              rest = preorder remain x hi
    
    8|
    Permalink
  • amit1agrawal
    3 years ago+ 0 comments

    an option to write code in Java should be provided. solved it in java but cannot submit there as I don't know any of the languages provided.

    8|
    Permalink
  • ezequiel
    6 years ago+ 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 !

    1|
    Permalink
  • rustedwizard
    1 year ago+ 0 comments

    F# solution with comment:

    open System
    
    let testBST input =
        let rec test input stack root =
            match input,stack with
            //whenever current number is smalller than root return false
            |(h::t),_ when h < root -> false
            //when top of stack is smaller then current number
            //make the top of stack the new root and pop the stack
            |(h::t),(x::s) when x < h -> test input s x 
            //if input is not empty and other states are not matched
            //push current number into stack
            |(h::t),_ -> test t (h::stack) root 
            //if all numbers a processed
            //means input is valid pre-order sequence of BST return true
            |[],_ -> true
            //if anything else happen throw an error
            |_ -> failwith "something goes wrong"
        test input [] -1
    
    [<EntryPoint>]
    let main argv =
        let num = Console.ReadLine()|>int
        let input = [
            for i in 1..num do
                //no need to know how many nodes in the tree so ignore it
                Console.ReadLine()|>ignore
                let temp = Console.ReadLine()
                yield temp.Split(" ")|>List.ofArray|>List.map(fun x -> x|>int)
        ]
        for i in input do
            if (testBST i) then printfn "%s" "YES"
            else printfn "%s" "NO"
        0 // return an integer exit code
    
    0|
    Permalink
  • djgorman
    6 years ago+ 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). :)

    0|
    Permalink
Load more conversations

Need Help?


View top submissions
  • Contest Calendar
  • Blog
  • Scoring
  • Environment
  • FAQ
  • About Us
  • Support
  • Careers
  • Terms Of Service
  • Privacy Policy
  • Request a Feature