Minimum Depth of Binary Tree
Easy · Graphs · Explanation and code example
Recursive Minimum Leaf Depth
How it works
A leaf requires both children to be absent. When one child is missing, the minimum depth must follow the existing child; taking the minimum with an empty child would incorrectly end the path early. When both exist, take the shallower subtree depth.
Steps
- Return zero for an empty root.
- Follow the existing child when the other is absent.
- Otherwise return one plus the smaller child depth.
Complexity
- Time: O(n).
- Space: O(h) recursion stack.
Things to watch for
- Minimum depth ends at a leaf, rather than a missing child.
- A chain’s minimum depth equals its full length.
- An empty tree has depth zero.
Python code example
class Solution:
def minDepth(self, root: TreeNode | None) -> int:
if not root:
return 0
if not root.left:
return self.minDepth(root.right) + 1
if not root.right:
return self.minDepth(root.left) + 1
return min(self.minDepth(root.left), self.minDepth(root.right)) + 1
C++ code example
class Solution {
public:
int minDepth(TreeNode* root) {
if (root == nullptr)
return 0;
if (root->left == nullptr)
return minDepth(root->right) + 1;
if (root->right == nullptr)
return minDepth(root->left) + 1;
return min(minDepth(root->left), minDepth(root->right)) + 1;
}
};
Source and license
Explanation by LC Tracker. Code adapted from walkccc / Peng-Yu Chen · MIT license. Node types are supplied by LeetCode where needed.