# What is the time complexity of recursion approach(Java)?

• Well, the recursion approach is pretty simple:

``````public int maxDepth(TreeNode root) {
if(root == null)
return 0;
return Math.max(maxDepth(root.left),maxDepth(root.right))+1;
}
``````

I just cannot figure out the time complexity of this solution. Somebody says it's O(n). Aren't `maxDepth(root.left)` and `maxDepth(root.right)` computed simultaneously, which would make the time complexity O(lgn)? Thanks.

• O(logN) on average,

O(N) on worst case if the tree has only left/right for each level.

• I think, the Math.max function cannot return until both left and right are returned, so it basically touches every node.

• The complexity is exactly O(n). The recursion would touch every node in the tree, for once. The function wont return until it does so.

• The time complexity is O(N) because the recursion traverse each node in the tree

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