Binary Tree Level-order traversal

Problem Statement:
Implement binary tree level-order traversal.

Analysis:
We usually use queue to realize BFS, the implementation is done in Sol 1. This is a standard BFS algorithm. It requires O(n) space and O(n) time, where n is the number of nodes in the tree.

However, recursion can be used to solve this problem as well, this algorithm is implemented in Sol 2. As we could see, we traverse the tree h time in order to print nodes in each level, where h is the tree height. This leads to the in-efficiency of this algorithm. However, it's good to know that recursion could be used in BFS problems. The overall time complexity is O(n^2), where n is the number of nodes in the tree.

Code:
Sol 1:

void levelOrderIter(TreeNode* root) {
    queue<TreeNode*> q;

    q.push(root);
    while (!q.empty()) {
        TreeNode* tmp=q.front();
        q.pop();
        cout<<tmp->val<<endl;

        if (tmp->left!=NULL) q.push(tmp->left);
        if (tmp->right!=NULL) q.push(tmp->right);
    }
    return;
}

Sol 2:

void levelOrder(TreeNode* root) {
    // height of tree
    int height=getHeight(root);
    // traverse each level
    for (int i=0; i<height; i++)
        printLevel(root, i);
    return;
}

void printLevel(TreeNode* node, int level) {
    if (node==NULL) return;

    if (level==0) {
        cout<<node->val<<endl;
        return;
    }

    printLevel(node->left, level-1);
    printLevel(node->right, level-1);
}

int getHeight(TreeNode* node) {
    if (node==NULL) return 0;
    int lHeight=getHeight(node->left);
    int rHeight=getHeight(node->right);
    return (lHeight>rHeight ? lHeight:rHeight)+1;
}