1.Maximum/Minimum Depth of Binary Tree

Given the root of a binary tree, return its maximum depth.

A binary tree's maximum depth is the number of nodes along the longest path from the root node down to the farthest leaf node.

Example 1:

Input: root = [3,9,20,null,null,15,7]
Output: 3

Example 2:

Input: root = [1,null,2]
Output: 2

Example 3:

Input: root = []
Output: 0

Example 4:

Input: root = [0]
Output: 1

Solution I : (Using level order traversal)

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

        TreeNode *t = root;
        queue<TreeNode *> q;
        q.push(root);
        int s = 0;
        while (!q.empty())
        {

            int k = q.size();

            while (k > 0)
            {
                TreeNode *p = q.front();
                q.pop();
                if (p->left != NULL)
                {
                    q.push(p->left);
                }
                if (p->right != NULL)
                {
                    q.push(p->right);
                }
                k--;
            }

            s++;
        }
        return s;
    }
};

This solution is based on level order tree traversal and finding the height.

Solution II: Recursive

class Solution
{
public:
    

    int maxDepth(TreeNode *root)
    {
       
        if(root == NULL){
            return 0;
        }
        
        int ldepth = maxDepth(root->left);
        int rdepth = maxDepth(root->right);
        return max(ldepth,rdepth) + 1;
    }
};

Minimum Depth of Binary Tree

Given a binary tree, find its minimum depth.

The minimum depth is the number of nodes along the shortest path from the root node down to the nearest leaf node.

Note: A leaf is a node with no children.

Example 1:

Input: root = [3,9,20,null,null,15,7]
Output: 2

Example 2:

Input: root = [2,null,3,null,4,null,5,null,6]
Output: 5

Solution

class Solution
{
public:
    int minDepth(TreeNode *root)
    {

        if (root == NULL)
        {
            return 0;
        }

        int ld = minDepth(root->left);
        int rd = minDepth(root->right);
        if (ld == 0)
        {
            return rd + 1;
        }
        else if (rd == 0)
        {
            return ld + 1;
        }
        return min(ld, rd) + 1;
    }
};