Approach #1 Iterative [Accepted]
Intuition and Algorithm
Idea is to traverse level by level. Whenever moving down to another level, increment height by 1 (height is initialized as 0),remove nodes of this level and add nodes of
next level. Count number of nodes at each level, stop traversing when count of nodes at next level is 0.
Java
public int maxDepth(TreeNode root) {
if(root==null){
return 0;
}
Queue<TreeNode> q=new LinkedList();
q.add(root);
int height=0;
while(1==1){
int count=q.size();
if(count==0){
return height;
}
height++;
while(count>0){
TreeNode newnode = q.peek();
q.remove();
if (newnode.left != null)
q.add(newnode.left);
if (newnode.right != null)
q.add(newnode.right);
count;
}
}
Complexity Analysis

Time complexity : O(n).

Space complexity : Maximum Space can be o(2^d). Where d is the depth of the tree.
Note
There are other iterative aproach using stacks,Inorder traversal, Postorder Traversal.
Refer: https://articles.leetcode.com/maximumheightofbinarytree/
Approach #2 Recursion [Accepted]
Idea is to first compute the max height of left subtree, then compute the max height of right subtree. Therefore, the max height of the current node is the greater of the two max heights + 1. For the base case, the current node is NULL, we return zero. NULL signifies there is no tree, therefore its max height is zero.
Algorithm
Java
public class Solution {
public int maxDepth(TreeNode root) {
if(root==null){
return 0;
}
int l=maxDepth(root.left)+1;
int r=maxDepth(root.right)+1;
int max=Math.max(l,r);
return max;
}
}
Complexity Analysis

Time complexity : O(n).

Space complexity : No additional space other than recursion overhead stack space.