SAMSUNG 49-Inch Odyssey G9

Because earth is not flat

Intuition

The maximum depth of a binary tree can be determined by finding the longest path from the root node to any leaf node. This involves recursively calculating the depth of each subtree and then taking the maximum value.

Approach

To solve this problem, we can use a recursive approach to traverse the tree. The base case is when the root is None, indicating an empty tree with a depth of 0. For a non-empty tree, we recursively calculate the depth of the left and right subtrees, then return the maximum of these depths plus one (to account for the current node).

Here are the steps:

1. Check if the root is None. If it is, return 0.
2. Recursively call maxDepth on the left child to find the depth of the left subtree.
3. Recursively call maxDepth on the right child to find the depth of the right subtree.
4. The depth of the current node is the maximum of the depths of the left and right subtrees plus one.

Complexity

Time Complexity:

O(N), where N is the number of nodes in the binary tree. Each node is visited once.

Space Complexity:

O(H), where H is the height of the tree. This is due to the space required for the recursion stack. In the worst case (for a completely unbalanced tree), the height is N, and in the best case (for a completely balanced tree), the height is log(N).

Code

C++

class Solution {
public:
    int maxDepth(TreeNode* root) {
        if (!root) {
            return 0;
        }
        
        int leftSubHeight = maxDepth(root->left);
        int rightSubHeight = maxDepth(root->right);
        
        return std::max(leftSubHeight, rightSubHeight) + 1;
    }
};

Python

# Definition for a binary tree node.
class TreeNode:
    def __init__(self, val=0, left=None, right=None):
        self.val = val
        self.left = left
        self.right = right

class Solution:
    def maxDepth(self, root: Optional[TreeNode]) -> int:
        if root is None:
            return 0

        leftSubHeight = self.maxDepth(root.left)
        rightSubHeight = self.maxDepth(root.right)

        return max(leftSubHeight, rightSubHeight) + 1

Java

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

        int leftSubHeight = maxDepth(root.left);
        int rightSubHeight = maxDepth(root.right);

        return Math.max(leftSubHeight, rightSubHeight) + 1;
    }
}

JavaScript

var maxDepth = function (root)
 {
    if (!root) return 0

    let leftSubHeight = maxDepth(root.left)
    let rightSubHeight = maxDepth(root.right)
    
    return Math.max(leftSubHeight, rightSubHeight) + 1
};