# 8ms Recursive/BFS C++ Solutions

• Well, this problem has the highest acceptance rate among all OJ problems. It has a very easy 1-line reursive solution. I am not sure whether this one can be called "DFS" so I only call it "recursive".

``````class Solution {
public:
int maxDepth(TreeNode* root) {
return root ? 1 + max(maxDepth(root -> left), maxDepth(root -> right)) : 0;
}
};
``````

Well, you may also solve it using a level-order traversal (BFS) with a queue.

``````class Solution {
public:
int maxDepth(TreeNode* root) {
int depth = 0;
if (!root) return depth;
queue<TreeNode*> level;
level.push(root);
while (!level.empty()) {
depth++;
int n = level.size();
for (int i = 0; i < n; i++) {
TreeNode* node = level.front();
level.pop();
if (node -> left) level.push(node -> left);
if (node -> right) level.push(node -> right);
}
}
return depth;
}
};``````

• Using pairs, 12ms:

``````class Solution {
public:
int maxDepth(TreeNode* root) {
if (!root) { return 0; }

int depth = 0;
queue<std::pair<TreeNode*, int>> lst;

lst.push(std::make_pair(root, 0));
while (!lst.empty()) {
std::pair<TreeNode*, int> curr = lst.front();
lst.pop();

TreeNode *leaf = curr.first;
int lvl = curr.second;

if (leaf) {
lst.push(std::make_pair(leaf->left, lvl + 1));
lst.push(std::make_pair(leaf->right, lvl + 1));
continue;
}

depth = max(depth, lvl);
}

return depth;
}
};``````

• Hi, kkamkou. I wonder what is the advantage of using `pair<TreeNode*, int>` if it will slow down your code (seen from the running time)?

• none, just as a variant.

• My std::pair solution was 8ms,

``````int maxDepth(TreeNode* root) {
if (root == nullptr) return 0;

std::queue<std::pair<int, TreeNode*>> nodes; // Depth, TreeNode*
nodes.push(std::pair<int, TreeNode*>(1, root));

// Iterate through each level, adding the next depth to the queue
int maxNodeDepth = 1;
while (nodes.size() > 0) {
std::pair<int, TreeNode*> pair = nodes.front();
nodes.pop();
auto currentDepth = pair.first;
TreeNode* currentNode = pair.second;
if (currentDepth > maxNodeDepth) {
maxNodeDepth = currentDepth;
}
if (currentNode->left != nullptr) {
nodes.push(std::pair<int, TreeNode*>(currentDepth+1, currentNode->left));
}
if (currentNode->right != nullptr) {
nodes.push(std::pair<int, TreeNode*>(currentDepth+1, currentNode->right));
}
}

return maxNodeDepth;
}``````

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.