3.1) Maximum Depth of Binary Tree

Given a binary tree, find its maximum depth. The maximum depth is the number of nodes along the longest path from the root node down to the farthest leaf node.

Sample Input:

Tree:
       3
      / \
     9   20
        /  \
       15   7

Expected Output:

3

In this example, the maximum depth of the binary tree is 3, as the longest path from the root node to a leaf node is 3 nodes.

Time and Space Complexity:

The time complexity of the algorithm is O(n), where ‘n’ is the number of nodes in the binary tree. We need to visit each node once to determine the maximum depth. The space complexity is O(h), where ‘h’ is the height of the binary tree. In the worst case, the recursion stack can grow to the height of the tree.

C++ solution:

#include <iostream>

// Definition for a binary tree node.
struct TreeNode {
    int val;
    TreeNode* left;
    TreeNode* right;
    TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
};

int maxDepth(TreeNode* root) {
    // Base case: if the root is null, the depth is 0
    if (root == nullptr) {
        return 0;
    }

    // Recursively compute the depth of the left and right subtrees
    int leftDepth = maxDepth(root->left);
    int rightDepth = maxDepth(root->right);

    // The depth of the current node is the maximum depth of its subtrees plus 1
    return std::max(leftDepth, rightDepth) + 1;
}

int main() {
    // Construct the binary tree for the sample input
    TreeNode* root = new TreeNode(3);
    root->left = new TreeNode(9);
    root->right = new TreeNode(20);
    root->right->left = new TreeNode(15);
    root->right->right = new TreeNode(7);

    // Find the maximum depth of the binary tree
    int depth = maxDepth(root);

    std::cout << "The maximum depth of the binary tree is: " << depth << std::endl;

    // Don't forget to free the allocated memory
    // ...

    return 0;
}

The maxDepth function recursively calculates the maximum depth of the binary tree. It starts from the root node and computes the depth of the left and right subtrees. The depth of the current node is the maximum depth of its subtrees plus 1.

In the given example, the function will correctly find that the maximum depth of the binary tree is 3, and the output will be 3.

As mentioned earlier, the time complexity is O(n) as we need to visit each node once, and the space complexity is O(h) due to the recursion stack, where ‘h’ is the height of the binary tree.