How would I print out a given range of numbers from a binary tree in an ascending order.
Like how can I get the range [3;6] from the picture without traversing the whole tree checking if it's within that range.
Help me with my assignment please
How would I print out a given range of numbers from a binary tree in an ascending order.
Like how can I get the range [3;6] from the picture without traversing the whole tree checking if it's within that range.
It's impossible.
It's an unsolved problem and I gave up on it years ago.
>Like how can I get the range [3;6] from the picture without traversing the whole tree checking if it's within that range.
are you asking how to check of every node value of the tree is >= 3 and <= 6 ?
You do a regular search to find the 3. (If current == 3 then done else if current < 3 then recurse with left child else recurse with right child.)
You do a regular search to find the 6.
You do a regular inorder traversal starting from the 3 until you reach the 6.
I should have clarified that the minimum and maximum values of the range don't need to be and probably aren't in the tree.
So if the nodes in the pic were 20 30 and I'm looking for 25. And now the problem is that the the node closest to 25 could be at the end of branch and all of the parents of the leaf are lower or bigger than the range which would make checks for a change from curr > low to curr < low useless.
>t.doesn't understand a binary tree NGMI
If the tree isn't sorted then you have to sort first. If the tree is sorted then your comment is dumb and you need to look into how a binary tree actually works.
If you are just trying to optimize then just do this
while min > root and max > root
root <- root.right
while min < root and max < root
root <- root.left
for i <- min ... max
cur <- root
while cur is not none
if cur == i
print i
else if cur > i
cur <- cur.right
else
cur <- cur.left
Even more optimization
while min > root and max > root
root <- root.right
while min < root and max < root
root <- root.left
for i <- min ... max
if root > i
root<- root.right
cur<- root
else
cur <- root.left
while cur is not none
if cur > i
cur <- cur.right
else if cur < i
cur <- cur.left
else
print i
break
It doesn't matter whether the start and end nodes are in the tree or not. In the process of looking for the start node you'll also find the place where it should've been, so your traversal simply starts from there. Similarly your traversal will end when you reach a node that is >= the end value, so either the value is in the tree and you stop when you == it, or the value is not in the tree and you stop when you > it.
I came up with somewhat good enough solution involving three recursive functions first gets into the interval than the second one traverses through the interval and if it hits a node which is out of bounds it calls a third functions which traverses the whole subtree of that node (right or left child depending on the side) .
Not the best but it's good enough I suppose. I found the process of looking for the min and max node a bit too complex to implement. But I might try it.
Thanks for the help guys
>I should have clarified that the minimum and maximum values of the range don't need to be and probably aren't in the tree.
So basically the problem is finding if yes or no any node of the tree is in the given range?
fricking hell, try to think more than 10s before asking a question next time
I could solve this problem for you, if I was paid to.
found the chinese student
cur <- root
for 3...6 -> i
while cur is not null
if cur == i
print i
else if i > cur
cur <- cur.right
else
cur <- cur.left
ngmi.
change your major.
the dancer degree will be about right.
you search for 3
then you traverse until you hit 6 (or a number greater therethan)
and then you kys
Why are you wasting your time trying to learn this shit? There are no jobs.
inorder traversal with if statement to check current value
>without traversing the whole tree checking if it's within that range.
it's not possible to guarantee that your range isn't going to be at the end of your search algorithm if you want it in ascending order. the best you can do is o(n).
>the best you can do is o(n)
actually O(M), or O(max(lg N, M)) if you want to be really pedantic.
where N is the number of nodes in the tree, and M is the number of nodes containing numbers within the specified range. You only need to traverse the subtree containing the specified range.
As a thought experiment for this, consider that you can re-root the tree such that the lowest valued node in the range is the root - this is doable in O(lg N). Cut off the left branch in O(1). Re-root the tree such that the highest valued node in the range is the root in O(lg N). Cut off the right branch in O(1). Now walk the remaining tree printing out the values in O(M) since this tree now only contains elements in the requested range. Now you can reassemble the tree by splicing in the right branch, rerooting at the min node and splicing back in the left branch.
This is a lot of stuff to code up, so it's nice that the properties of an ordered tree means that the rerooting and cutting/splicing code isn't actually needed, it's a matter of your traversal/printing algorithm maintaining the proper perspective of the tree as it's walking through it.
If you've already got a library of splaying functions in hand, and don't care about reader safety in a multithreaded environment then the thought experiment version probably the best solution simply because it's completely linear and trivially proven correct while having the same big O as the custom solution.
you can make a map function that requires a position. With the position you can get the next most efficient moves to your destination
map<int> tree;
auto begIt = tree.lower_bound(3);
auto endIt = tree.lower_bound(6);
for (auto it = begIt; it != endIt; ++it) cout << @it;
Even without access to C++ standard library, algorithm holds:
1. create 'getNext' to get from one node to another
2. find first node
3. find last node
4. traverse
Hope that helps, anon. You are the best!