Determining the number of levels in a binary tree via algorithm

Question

I am trying to create a divide-and-conquer algorithm for computing the number of levels in a binary tree. In particular, the algorithm should return 0 and 1 for the empty and single-node trees, respectively. Once the algorithm has been created, I need to define the efficiency class of the algorithm.

Answer 1

Your algorithm should look something like the following:

height(tree: BinaryTree) {
    if (tree==null) {
        return 0;
    }
    else {
        return max(height(tree.left), height(tree.right)) + 1;
    }
}

The efficiency of this algorithm is O(n), because each iteration spends a constant time in each node, with each node being visited only once.

Answer 2

Do a level order Traversal of the binary tree using a Queue Data structure. And after completing each Level, insert a dummy node to denote that the level has been completed. 

Partial C code + Psuedocode:
int num_of_levels(Node *root)
{
    if(root == NULL) return
    Initialise a Queue
    Add root to Q
    Add a Dummy Node(NULL pointer) to Queue
    no_of_levels = 1
    while(Q is not enmpty)
    {
        Dequqe a node from Queue and assign it to root
        if(root == NULL and Q is not empyy)
        {
            add NULL pointer(dummy node) to Q
            no_of_levels ++ 
        }
        if(root->left)
          add root->left element to Q
        if(root->right)
          add root->right element to Q         
    }
  return no_of_levels
}