104. Maximum Depth of Binary Tree

Check out the problem description here.

Maximum Depth of Binary Tree - LeetCode

Approach 1:

Using recursive(DFS)

For any node the max depth is 1+max(left,right)

class Solution:
    def maxDepth(self, root: TreeNode) -> int:
        return self.rec(root)
    def rec(self,root):
        if not root:
            return 0
        left=self.rec(root.left)
        right=self.rec(root.right)
        return max(left ,right)+1

Time: O(n)

Space: O(logn)-> auxiliary space, n is total number of nodes

Approach 2:

Using level order(BFS) , that is using a queue

class Solution:
    def maxDepth(self, root: TreeNode) -> int:
        q=[]
        counter=0
        if root:
            q=[root]
        while(q):
            size = len(q)
            for i in range(size):
                if q[0].left:
                    q.append(q[0].left)
                if q[0].right:    
                    q.append(q[0].right)
                    
                q.pop(0)
            counter+=1
        return counter

Time: O(n)

Space: O(k) that is the max space occupied in the queue

k= max number of nodes at a level (actually can be approximated to n )