How to find the height of a binary tree without using recursion and level order traversal?

Question

I came up with preorder traversal for finding the height of a tree.

void preHeight(node * n)
{
    int max = 0,c = 0;
    while(1)
    {
        while(n)
        {
            push(n);
            c++;
            if(c>max)
                max = c;
            n= n->left;
        }
        if (isStackEmpty())
            return max;
        n = pop();
        if(n->right)  //Problem point
            c--;
        n=n->right;
    }
}

I get the height correct but I'm not sure if my method is correct. What I do is I increment my counter c till the leftmost node and then, if I move up I reduce it in case I need to move right, and then repeat the entire exercise. Is that correct?

Answer 1

Consider the following tree -

    o
   / \
  o   o
 /     \
o       o 

You will reach the end of leftmost branch with c==2, then pop the nodes on the way up, but only decrement c for nodes with a right child, when in fact you should decrement it on each pop since it means you went a level up, regardless of other children. In this case you'll reach the top node, decrement once, and then start descending from the root with c==1, eventually reaching 3.

If you remove the condition it should work. Alternatively, you can keep the value of c per each level instead of restoring it with the decrements - you could either push it into a separate stack alongside the node pointers, or you could convert the code to be recursive, with c (and the current node) as local variables (basically this is the same thing, except that the compiler maintains the stack for you).