# Java One Recursive and Two Iterative Solutions With Explanations

• Solution 1: Recursive Solution

``````// Method 1: Recursion Solution
// Time: O(n)
// Space: O(n)
public int maxDepth(TreeNode root) {
// base case
if (root == null) {
return 0;
}
// Find the maxDepth of left sub tree
int left = maxDepth(root.left);
// Find the maxDepth of right sub tree
int right = maxDepth(root.right);
// return the max depth of left / right subtree + 1(root)
return 1 + Math.max(left, right);
}
``````

Solution 2: Iterative BFS

``````// Method 2: Iterative BFS
// Time: O(n)
// Space: O(n)
public int maxDepth(TreeNode root) {
// Corner case
if (root == null) {
return 0;
}
// Use queue to help level order traversal
queue.offer(root);
// count the number of levels of tree
int count = 0;
while (!queue.isEmpty()) {
for (int size = queue.size(); size > 0; size--) {
TreeNode cur = queue.poll();
if (cur.left != null) {
queue.offer(cur.left);
}
if (cur.right != null) {
queue.offer(cur.right);
}
}
// Finished current level, count++
count++;
}
return count;
}
``````

Solution 3: Iterative DFS

``````// Method 3: Iterative DFS
// Time: O(n)
// Space: O(n)
public int maxDepth(TreeNode root) {
// Corner case
if (root == null) {
return 0;
}
// Use a stack to help iterative dfs
// Use another stack to count levels
stack.offerLast(root);
level.offerLast(1);
int max = 0;
while (!stack.isEmpty()) {
TreeNode curNode = stack.pollLast();
int curLevel = level.pollLast();
// Update max depth if possible
max = Math.max(max, curLevel);
if (curNode.left != null) {
stack.offerLast(curNode.left);
level.offerLast(curLevel + 1);
}
if (curNode.right != null) {
stack.offerLast(curNode.right);
level.offerLast(curLevel + 1);
}
}
return max;
}
``````

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