breadth first tree, max distance from root to leaf

Question

I am trying to compute the # of nodes in the longest path from root to leaf of a binary tree. Given the below code, I have two questions:

1) Is using a queue in the following way equivalent to a breadth-first walk of the tree? 2) Is this an accurate way to do so? The function prototype is fixed, so I can't see doing it recursively if I can't pass state (like depth_count) between recursive calls.

The function outputs 5 for the tree {0,2,4,1,#,3,-1,5,1,#,6,#,8} and should output 4.

int maxDepth(TreeNode *root){ 
    int depth_count=0, i;
    queue<TreeNode*> ns;
    TreeNode* curr;

    if (root){
        ns.push(root);        

       while (!ns.empty()){
            depth_count++;
            for (i=0; i < ns.size(); i++){
                curr = ns.front();
                if (curr->left)
                    ns.push(curr->left);
                if (curr->right)
                    ns.push(curr->right);
                ns.pop();
            }

        }//endwhile
    }//endif
    return depth_count;
}

Answer 1

I don't think it is correct the for loop looks a little strange. If you don't want to do it recursively and breadth first I would save the depth in the queue along with the node.

int maxDepth(TreeNode *root){ 
  int depth=0;
  queue<pair<TreeNode*, int> > ns;
  pair<TreeNode*, int> curr;

  if (root){
    ns.push(make_pair(root, 1));

   while (!ns.empty()){
      curr = ns.front();
      depth = max(depth, curr.second);
      if (curr.first->left)
        ns.push(make_pair(curr.first->left, curr.second+1));
      if (curr.first->right)
        ns.push(make_pair(curr.first->right,curr.second+1));
      ns.pop();

    }//endwhile
  }//endif
  return depth;
}

Edit: Another way would be to use the code you got but not using ns.size() in the for loop, this will grow or shrink as you add and remove nodes in the queue and you will not traverse a single depth. Instead you need to save ns.size() before you enter the for loop so you only traverse a single depth of the tree each time you enter the for loop.