Question: On your b-tree code, wouldn't the lh operand in the return recursively execute before the rh, throwing off the original reqs?
Asked by Will (24.234.85.x) on February 6 2013, 10:44pm
Reply on February 7 2013, 2:49am (edited at February 7 2013, 3:42am):Yes (it processes left before right), but no, it does what (as I understood, anyway) the requirements specified, since each top level call to the recursive function only prints a single level of the tree, so the left-to-rightness is what you want. Edit: here, this might be easier to understand (exact same function, just more clear code):
f(h, levelToPrint, currentLevel) {
if (currentLevel > levelToPrint) return 0;
if (!h) {
if (currentLevel == levelToPrint) print("(null)");
return 0;
}
if (currentLevel == levelToPrint) {
print(h);
return 1;
}
return f(h.left,levelToPrint, currentLevel+1) + f(h.right,levelToPrint, currentLevel+1);
}
levelToPrint=0;
while (f(tree,levelToPrint++,0)) print("\n");
Question: What's a good algorithm to display a binary tree from the top down one level at a time left to right?
Asked by Will (24.234.85.x) on February 5 2013, 10:34pm
Reply on February 6 2013, 4:11am (edited at February 6 2013, 4:37am):The obvious way I'd imagine doing it would be O(N*log(N)), which seems reasonable enough I guess?
f(h, level) {
if (level == 0) print(h); // h might be null
return h && level >= 0 ? level==0 ? 1 : f(h.left,level-1) + f(h.right,level-1) : 0;
}
l=0;
while (f(tree,l++)) print("\n");
Edit: updated to print null leaves for levels that are printed...
Edit: further updated to overuse the tertiary operator. Regretting this, here is the less obfuscated version:
f(h, level) {
if (level < 0) return 0;
if (!h) {
if (level == 0) print("(null)");
return 0;
}
if (level == 0) {
print(h);
return 1;
}
return f(h.left,level-1) + f(h.right,level-1);
}
l=0;
while (f(tree,l++)) print("\n");