Deepest Node in a Binary Tree

[Question]
Find the deepest node in a binary tree.

[Analysis]
In BFS (Breadth First Search), the last node visited is the deepest node in a tree (not necessarily a Binary Tree; it applies to any trees). Time complexity is O(N), N is the number of nodes in the tree.

Using DFS (Depth First Search) works too. Explore every node and count the depth of each leaf node by pre-order DFS. Although the time complexity is also O(N), it needs more code.

Another advantage of BFS is, it can provide information like, the number of nodes at a given level (shown in code sample #2 below).

[Solution]

//  -- CODE #1 --

//class Node {
//public:
//    Node* left, *right;
//    int value;
//};

Node* deepestNode( Node* root )
{
    if (root==NULL) return NULL;

    queue<Node*> que;
    que.push( root );

    Node *p;
    while (!que.empty()) {
        p = que.front();
        que.pop();
        if (p->left) que.push(p->left);
        if (p->right) que.push(p->right);
    }

    return p;
}

// -- CODE #2 --
//-- get the number of nodes in a given level of BST
//
int NumberAtLevel( Node* root, int level )
{
    if (root==NULL || level <0) return 0;
    if (level ==0) return 1;

    queue<Node*> que;
    que.push( root );
    int num = 1;

    Node *p=NULL;
    while (!que.empty()) {
        p = que.front();
        que.pop();
        num--;

        if (p->left) que.push(p->left);
        if (p->right) que.push(p->right);

        if (num==0) {
            level --;
            num = que.size();
            if (level==0) return num;
        }
    }

    return 0; //level is over the depth of tree;
}