since we are checking to see if the tree is sorted, we cannot skip some nodes, we must check them all.
by checking them all once, (or twice for that matter) we are doing this in O(N) time and that cannot be made to work any faster.
i guess what i still don't get is how the check function could work at any other speed.
i am assuming that even though it does not work, your original function still runs at speed O(N) because it examines each node once, but i cannot see how it would run at O(N^2) or anything like that...
i am guessing my life would be easier if i just ignored that last sentence in the assignment (this should be done at O(N) speed) because I already did it, but I would feel better if i understood the concept for the long run
Maybe I should say a bit more directly about this problem.
Here is how it could be worse
It is easy to check in O(N) time to see if a node is in the right
order
with it's children.
Given a tree of size N, this takes a finite number of steps at
each node,
for a total of O(N) time.
However, this doesn't solve the problem. There are
trees that satisfy this local property but which do not satisfy the
global property. Clearly the disagreement will need to be at
least 2 generations apart.
Here is an algorithm that is correct, but too slow
If you think about the worst case (all left links are null: you
have a linked list) you can see that this is quadratic in N. It
is our old friend n*(n-1)/2, in fact. I'll let you think about
the best case (an evenly balanced tree) and see how bad you think that
is.
Try nice trees with 3, 7, 15, etc. nodes.
So the problem is to spell out a solution in more detail than I
have offered, and to try to find a solution that doesn't take more
than a constant number of steps per node. Clearly the second
solution can have multiple steps per node.
My best advice would be to write down a solution, and come back
and improve it if inspriation strikes. In the meantime, you will
have cleared one more problem off your plate, and you can focus on
problem #5.
- jeff parker
