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");
Comment: