Maximum Depth of Binary Tree

easy Trees

Given the root of a binary tree, return its maximum depth. The maximum depth is the number of nodes along the longest path from the root node down to the farthest leaf node. The tree can have between 0 and 10,000 nodes with values in the range [-100, 100].

Example

Output: 3

The longest path from root to leaf is 3 → 20 → 15 (or 3 → 20 → 7), which passes through 3 nodes.

The depth of a tree is 1 plus the maximum depth of its left and right subtrees. A null node has depth 0. Recurse down to the leaves and let the answers bubble back up.

Why this works

The depth of any node equals 1 (for itself) plus the depth of its deepest child. By recursing to the leaves where null returns 0, each call naturally computes the height of its subtree and passes it back up. The root ends up with the maximum depth of the entire tree.

Step by step

Base case — if the node is null, return 0 because there is no depth to count.
Recurse into both subtrees — ask the left child and right child for their depths.
Combine results — take the maximum of the two depths and add 1 for the current node.

Time: O(n) Space: O(h)

class TreeNode {
    int val;
    TreeNode left, right;
    TreeNode(int val) { this.val = val; }
}


class Solution {
    public int maxDepth(TreeNode root) {
        if (root == null) {
            return 0; // null node contributes zero depth
        }
        return 1 + Math.max(maxDepth(root.left), maxDepth(root.right)); // take the deeper subtree
    }
}

struct TreeNode {
    int val;
    TreeNode *left, *right;
    TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
};


class Solution {
public:
    int maxDepth(TreeNode* root) {
        if (!root) {
            return 0; // null node contributes zero depth
        }
        return 1 + max(maxDepth(root->left), maxDepth(root->right)); // take the deeper subtree
    }
};

class TreeNode:
    def __init__(self, val=0, left=None, right=None):
        self.val = val
        self.left = left
        self.right = right


def maxDepth(root: TreeNode | None) -> int:
    if not root:
        return 0  # null node contributes zero depth
    return 1 + max(maxDepth(root.left), maxDepth(root.right))  # take the deeper subtree