Maximum Depth of Binary Tree

Problem Statement

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

Rules and Constraints

• The binary tree is not explicitly defined, but you can assume that it is provided as a structure with standard nodes (value, left child, right child).
• For the purpose of this problem, assume that a NULL/Nil/None value represents an empty subtree.
• The input tree is not necessarily a complete or balanced tree.

Time Complexity Requirements

The solution should return the maximum depth of the binary tree in O(n) time complexity, where n is the number of nodes in the tree. This implies that you should not be able to traverse the tree more than once.

Space Complexity Requirements

The solution should use O(h) space complexity, where h is the height of the tree, which in the worst case is equal to n. This implies that you should avoid recursive solutions unless you can handle them with iterative methods and proper backtracking, to avoid excessive stack usage.

The goal is to find the optimal solution that provides the required time and space complexity bounds while accurately calculating the maximum depth of the provided binary tree.

Example

Input: {"root":[3,9,20,null,null,15,7]} Output: 3