You are Here: Home

# Binary search trees - help! Watch

1. 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.
2. 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)
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)
3. 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.
4. Yeah, I think I got it now, thank you guys! =D

TSR Support Team

We have a brilliant team of more than 60 Support Team members looking after discussions on The Student Room, helping to make it a fun, safe and useful place to hang out.

This forum is supported by:
Updated: December 13, 2010
Today on TSR

### Degrees to get rich!

... and the ones that won't

### Cambridge interviews pour in...

Discussions on TSR

• Latest
• ## 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
Useful resources

## Groups associated with this forum:

View associated groups
Discussions on TSR

• Latest
• ## 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

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