Binary Tree Maximum Depth Calculation Solution

Problem Statement

### Maximum Depth of a Binary Tree #### Problem Statement Given a binary tree, find the maximum depth of the tree. #### Example Input: Output: `3` Explanation: The maximum depth of the tree is 3, which is the path from the root node (3) to the leaf node (15 or 7). #### Solution #### Explanation * The `maxDepth` function takes a `TreeNode*` as input and returns the maximum depth of the tree. * If the input `root` is `NULL`, the function returns 0, indicating an empty tree. * Otherwise, the function recursively calculates the maximum depth of the left and right subtrees by calling `maxDepth` on `root->left` and `root->right`. * The maximum depth of the tree is then determined by taking the maximum depth of the left and right subtrees and adding 1 (for the current node). * In the `main` function, a sample binary tree is created, and the `maxDepth` function is called to calculate and print the maximum depth of the tree. ### Time Complexity The time complexity of this solution is O(n), where n is the number of nodes in the tree, since each node is visited once. ### Space Complexity The space complexity of this solution is O(h), where h is the height of the tree, due to the recursive call stack. In the worst case, the tree is completely unbalanced, and the space complexity becomes O(n).