Hey there! Sign in to join this conversationNew here? Join for free
    • Thread Starter
    Offline

    2
    ReputationRep:
    The exercise says:

    Write a function that receives a binary search tree "t" and two integers "n" and "m", and returns a list containing the values of "t" such that that n <= value <= m.

    I can't think of an algorithm that will do this Any ideas?
    Thanks!

    PS: I'm not allowed to add every single value of the tree to the list and then cutting out the list.
    Offline

    0
    ReputationRep:
    You could write a recursive tree traversal algorithm and just check each node for your constraints before adding them to your list.

    something along the lines of this maybe?
    Spoiler:
    Show

    Code:
    //pseudocode for tree_search
    tree_search(tree t, integer n, integer m)
    {
         if(t.left != null)
             tree_search(t.left,n,m)
         if (t >= n) && ( t <= m)
             add_to_list(t)
         if (t.right != null)
             tree_search(t.right,n,m)
        return list
    }


    I didn't go through any detail on adding found elements to the list, but that should be fairly trivial. Any questions on why/how this works give me a shout.
    (Also if I buggered up remembering tree-traversals and its actually broked tell me xD)
    Offline

    19
    ReputationRep:
    As above but I think you also could omit traversal of right branches where current node <n and left branches where current node >m
    cos all nodes down those branches would be outside the required range.
    • Thread Starter
    Offline

    2
    ReputationRep:
    Yeah, I think I got it now, thank you guys! =D
 
 
 
  • See more of what you like on The Student Room

    You can personalise what you see on TSR. Tell us a little about yourself to get started.

  • Poll
    Did TEF Bronze Award affect your UCAS choices?
    Useful resources
  • See more of what you like on The Student Room

    You can personalise what you see on TSR. Tell us a little about yourself to get started.

  • The Student Room, Get Revising and Marked by Teachers are trading names of The Student Room Group Ltd.

    Register Number: 04666380 (England and Wales), VAT No. 806 8067 22 Registered Office: International House, Queens Road, Brighton, BN1 3XE

    Quick reply
    Reputation gems: You get these gems as you gain rep from other members for making good contributions and giving helpful advice.