Alright, here’s the answer:
int depth(Tree t) {
if ( t == null )
return 0;
return 1 + max(depth(t.left),depth(t.right));
}
My boss did it in one line by eschewing if statements:
int depth(Tree t) {
return (t == null)? 0 : 1 + max(depth(t.left),depth(t.right));
}
Pages: 1 2 3
This entry was posted
on Thursday, December 9th, 2004 at 12:28 am and is filed under Nerd Stuff.
You can follow any responses to this entry through the RSS 2.0 feed.
You can leave a response, or trackback from your own site.
December 11th, 2004 at 9:50 am
I feel all special cause I came up with your boss’s answer. But, I don’t think it’s all that hard of a problem. I guess a CS background leads you to think about recursion whenever you think about trees, so maybe the classically trained programmers have an advantage over the rest of coding humanity. But, still, anyone who’s done any XML work has probably had to do some recursive tree walking, so a mid-level IT-ish dev ought to have no issue recognizing the solution. I may start asking this at interviews–I’m getting bored with asking people to write a ‘for’ loop.
December 13th, 2004 at 1:16 pm
Yeah, maybe it’s not too hard for non CS people, but I really don’t think an incurious person would get it, even if they did XML. They’d probably do loops or use Xpath.
..and don’t forget how many people fail your for loop test.
By the way, comments don’t appear until I approve them, otherwise, I get spam.