Question

Write a routine to list out the nodes of a binary tree in level-order. List the root, then nodes at depth 1, followed by nodes at depth 2, and so on.

You must do this in linear time. Prove your time bound.

EXPERT ANSWER

- void level_order_traversal(node* root)
- {
- int h = getHeight(root);