Leetcode 104. Maximum Depth of Binary Tree

Problem Explanation

The problem asks to find the maximum depth of a binary tree. The maximum depth is defined as the number of nodes along the longest path from the root node down to the farthest leaf node. A leaf node is defined as a node with no children.

For instance, given the binary tree:

1
2plaintext
3    3
4   / \
5  9  20
6    /  \
7   15   7

The maximum depth is 3, because the longest path is from root node 3 to leaf node 7, which contains 3 nodes.

To solve this problem, we will use a Depth-First Search (DFS) recursive approach. Starting from the root, we will traverse each branch of the tree. For each node, we add 1 to the maximum depth of its left or right branch (whichever is greater), and then return the result to the higher level. The base case is when a node is null, in which case the depth is 0.

Python Solution

1
2python
3class TreeNode:
4    def __init__(self, x):
5        self.val = x
6        self.left = None
7        self.right = None
8
9class Solution:
10    def maxDepth(self, root: TreeNode) -> int:
11        # Base case: if root is null, return 0
12        if not root:
13            return 0
14        
15        # Recursive case: return 1 + maximum between left and right depths
16        return 1 + max(self.maxDepth(root.left), self.maxDepth(root.right))

Java Solution

1
2java
3class TreeNode {
4      int val;
5      TreeNode left;
6      TreeNode right;
7      TreeNode(int x) { val = x; }
8 }
9
10class Solution {
11    public int maxDepth(TreeNode root) {
12        // Base case: if root is null, return 0
13        if (root == null) {
14            return 0;
15        } else {
16            // Recursive case: return 1 + maximum between left and right depths
17            return 1 + Math.max(maxDepth(root.left), maxDepth(root.right));
18        }
19    }
20}

JavaScript Solution

1
2javascript
3function TreeNode(val, left, right) {
4    this.val = (val===undefined ? 0 : val)
5    this.left = (left===undefined ? null : left)
6    this.right = (right===undefined ? null : right)
7}
8
9var maxDepth = function(root) {
10    // Base case: if root is null, return 0
11    if (root === null) {
12        return 0;
13    } else {
14        // Recursive case: return 1 + maximum between left and right depths
15        return 1 + Math.max(maxDepth(root.left), maxDepth(root.right));
16    }
17};

C++ Solution

1
2cpp
3struct TreeNode {
4    int val;
5    TreeNode *left;
6    TreeNode *right;
7};
8
9class Solution {
10public:
11    int maxDepth(TreeNode* root) {
12        // Base case: if root is null, return 0
13        if (root == nullptr)
14            return 0;
15        
16        // Recursive case: return 1 + maximum between left and right depths
17        return 1 + max(maxDepth(root->left), maxDepth(root->right));
18    }
19};

C# Solution

1
2csharp
3public class TreeNode {
4    public int val;
5    public TreeNode left;
6    public TreeNode right;
7}
8
9public class Solution {
10    public int MaxDepth(TreeNode root) {
11        // Base case: if root is null, return 0
12        if (root == null) {
13            return 0;
14        } else {
15            // Recursive case: return 1 + maximum between left and right depths
16            return 1 + Math.Max(MaxDepth(root.left), MaxDepth(root.right));
17        }
18    }
19}

In all the solutions above, we recursively calculate the depth of the left and right branches of a node, then take the maximum between the two and add 1 to represent the current node. We continue doing this until we reach the leaf nodes, which have a depth of 0 since they do not have any children. This way, we can efficiently calculate the maximum depth of a binary tree.## Ruby Solution

1
2ruby
3class TreeNode
4  attr_accessor :val, :left, :right
5  def initialize(val, left = nil, right = nil)
6    @val = val
7    @left = left
8    @right = right
9  end
10end
11
12def max_depth(root)
13  # Base case: if root is null, return 0
14  return 0 unless root
15
16  # Recursive case: return 1 + maximum between left and right depths
17  1 + [max_depth(root.left), max_depth(root.right)].max
18end

Similar to the Python, JS, Java, C++, and C# solutions, the Ruby solution uses a recursive approach to calculate the maximum depth of a binary tree. The base case returns 0 when a null node is encountered (indicative of having reached a leaf node). The recursive case selects the maximum depth between the left and right subtrees and adds 1 for the current node to this maximum value to calculate the ongoing depth.

Closure Note

In conclusion, the key point to solve this problem is understanding how to use recursion to traverse a binary tree. Once you comprehend the depth-first search (DFS) recursion mechanism, you can easily adapt it to calculate various properties of a binary tree, such as its maximum depth, minimum depth, number of nodes, etc. This problem is a good example of how recursion can simplify problems dealing with tree-like data structures.