NUHMAN.com

Introduction

LeetCode 104: Maximum Depth of Binary Tree asks you to determine the maximum depth of a binary tree. The depth of a binary tree is the number of nodes along the longest path from the root node to the farthest leaf node.

This problem is commonly solved using Depth-First Search (DFS), which allows us to recursively explore each subtree and compute the maximum depth at each level.

Problem Statement

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

Example:

go

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

Input:
    [1]
Output:
    1

Input:
    []
Output:
    0

Approach:

Depth-First Search (DFS) Approach

The maximum depth of a binary tree can be found by exploring both the left and right subtrees recursively and returning the greater depth between the two subtrees, plus one for the current node.

Steps:

1. Base Case: If the node is nil, the depth is 0 because there are no nodes to traverse.
2. Recursive Case: For every node, recursively compute the maximum depth of the left and right subtrees.
3. Return the Maximum Depth: The depth of a node is the maximum depth of its left or right child plus one (for the current node).

Go Implementation

DFS Solution to Calculate Maximum Depth

go

package main

// TreeNode represents the structure of a binary tree node.
type TreeNode struct {
    Val   int
    Left  *TreeNode
    Right *TreeNode
}

// maxDepth calculates the maximum depth of a binary tree using DFS.
func maxDepth(root *TreeNode) int {
    // Base case: if the node is nil, return 0.
    if root == nil {
        return 0
    }
    
    // Recursively compute the depth of the left and right subtrees.
    leftDepth := maxDepth(root.Left)
    rightDepth := maxDepth(root.Right)
    
    // Return the greater depth of the two subtrees plus 1 for the current node.
    if leftDepth > rightDepth {
        return leftDepth + 1
    } else {
        return rightDepth + 1
    }
}

Explanation:

1. TreeNode Structure:

• The TreeNode structure represents a node in a binary tree, containing a value (Val), and pointers to the left (Left) and right (Right) children.

1. maxDepth Function:

• The maxDepth function is a recursive function that computes the maximum depth of the binary tree.
• If the root is nil, it returns 0 because an empty tree has no depth.
• For each node, the function recursively calls itself on the left and right children, computes their respective depths, and returns the greater of the two depths plus one for the current node.

1. Base Case: If the node is nil, the depth is 0.
2. Recursive Case: The function calls itself on both left and right subtrees to find their depths, and the maximum of the two depths is chosen.

Time and Space Complexity

MetricComplexityTime ComplexityO(n)Space ComplexityO(h)

Where:

• n is the number of nodes in the binary tree.
• h is the height of the tree.

Time Complexity:

• The function visits each node exactly once. Therefore, the time complexity is O(n), where n is the number of nodes in the tree.

Space Complexity:

• The space complexity is determined by the maximum recursion depth, which is proportional to the height of the tree. In the worst case (a skewed tree), the recursion depth could be O(n), where n is the number of nodes.
• For a balanced tree, the space complexity will be O(log n) because the recursion depth will be proportional to the height of the tree.

Edge Cases

1. Empty Tree:

• Input: root = nil
• Output: 0
• Explanation: An empty tree has no nodes, so the depth is 0.

1. Single Node Tree:

• Input: root = [1]
• Output: 1
• Explanation: A tree with only one node has a depth of 1.

1. Balanced Binary Tree:

• Input: root = [3, 9, 20, null, null, 15, 7]
• Output: 3
• Explanation: The tree has three levels, so the maximum depth is 3.

1. Right-skewed Tree:

• Input: root = [1, null, 2, null, 3]
• Output: 3
• Explanation: A right-skewed tree has a depth equal to the number of nodes.

1. Left-skewed Tree:

• Input: root = [1, 2, null, 3]
• Output: 3
• Explanation: A left-skewed tree has a depth equal to the number of nodes.

Conclusion

LeetCode 104: Maximum Depth of Binary Tree is a straightforward problem that tests your understanding of binary tree traversal. Using Depth-First Search (DFS) with recursion, we can efficiently compute the maximum depth of the tree. The solution is optimal with a time complexity of O(n) and a space complexity of O(h), where n is the number of nodes and h is the height of the tree. This problem is commonly encountered in various tree-related problems and is a useful exercise in mastering tree traversal techniques.